# Breadth first search on trees in Haskell

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
where
-- 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


bfs feasible interesting branches 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