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] _______________________________________________ Haskell-Cafe mailing list [email protected] http://www.haskell.org/mailman/listinfo/haskell-cafe
