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

[Johannes Waldmann]

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.)


J. W.

-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 260 bytes
Desc: OpenPGP digital signature
Url : http://www.haskell.org/pipermail/haskell-cafe/attachments/20100322/b1519f04/signature.bin