I'm writing a breadth first search algorithm in Haskell that supports pruning. It is guaranteed that the search will never encounter nodes that have been visited before, so I implemented the search as a filter along a stream of candidates.

I'm concerned about the efficiency of the code. Is there some slow, bad-practice code that I can try to avoid? What are some possible ways to optimize the code? Other feedback is also welcome!

bfs :: (a -> Bool) -- ^ Goal if evaluates to True
    -> (a -> Bool) -- ^ Prune if evaluates to False
    -> a  -- ^ Starting point of search
    -> (a -> [a])  -- ^ Branches at a point
    -> [a]  -- ^ Goals
bfs predicate prune a0 branch = filter predicate searchspace
        -- An elegant solution
        -- searchspace = a0 : (branch =<< searchspace)
        -- However, this solution <<loop>>'s when the search is finite
        searchspace = concat $ takeWhile (not.null) epochs
        epochs = [a0] : map (\as -> [ a' | a <- as, prune a, a' <- branch a]) epochs

1 Answer 1



bfs feasible interesting branches tree = 
  filter feasible . 
  concat . takeWhile(>[]) .
  iterate(concatMap branches . filter interesting)[tree] 

is about as efficient as you can get if you also prune some of your finds. Otherwise you can save some memory by pruning branches immediately after their generation as in filter interesting . concatMap branches


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.