Johannes Waldmann wrote:
Dear all, there is this neat "one-line" BFS implementation
bfs :: Eq a => ( a -> [a] ) -> a -> [a] bfs next start = let xs = nub $ start : ( xs >>= next ) in xs
but it has a problem: it only works for infinite graphs. This is fine:
take 20 $ bfs ( \ x -> [2*x, x+1] ) 1
but this is not:
take 20 $ bfs ( \ x -> filter (>0) [ div x 2, x - 1 ] ) 10
Is there a nice way to repair this? (I know how to code a BFS but here I'm asking for a one-liner.)
There is a neat trick to handle the finite case which I first read about in Leon P. Smith's article Lloyd Allison’s Corecursive Queues: Why Continuations Matter. http://themonadreader.wordpress.com/2009/07/29/issue-14/ Namely, you have to keep track of the "current" queue size so that the program doesn't hang when the queue becomes empty: bfs' f x = let xs = more 1 (x:xs) in x:xs where more 0 _ = [] more n (x:xs) = f x ++ more (n + length (f x) - 1) xs Unfortunately, this cannot be made to work with nub because that would screw up the size calculation. Regards, Heinrich Apfelmus -- http://apfelmus.nfshost.com