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