Breadth first search on trees in Haskell

Question

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

Answer 1

Your

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