[Haskell-cafe] breadth first search one-liner?
waldmann at imn.htwk-leipzig.de
Mon Mar 22 06:02:32 EDT 2010
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 )
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.)
-------------- next part --------------
A non-text attachment was scrubbed...
Size: 260 bytes
Desc: OpenPGP digital signature
Url : http://www.haskell.org/pipermail/haskell-cafe/attachments/20100322/b1519f04/signature.bin
More information about the Haskell-Cafe