[Haskell-cafe] Re: breadth first search one-liner?

[Heinrich Apfelmus]

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