[Haskell-cafe] Re: breadth first search one-liner?
Heinrich Apfelmus
apfelmus at quantentunnel.de
Thu Mar 25 04:36:09 EDT 2010
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
More information about the Haskell-Cafe
mailing list