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

[Ross Paterson]

On Mon, Mar 22, 2010 at 11:02:32AM +0100, 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?

bfs :: (a -> [a]) -> a -> [a]
bfs f s = concat $ takeWhile (not . null) $ iterate (>>= f) [s]