On Fri, May 16, 2008 at 07:58:40AM -0400, Dan Doel wrote:
On Friday 16 May 2008, leledumbo wrote:
I don't know how Haskell should behave on this. Consider this function: elemOf (x,y) = (x,y) `elem` [ (a,b) | a <- [0..], b <- [0..] ]
FYI: The control-monad-omega package on hackage.haskell.org can handle this sort of thing (liberties taken with ghci formatting):
Prelude> :m + Control.Monad.Omega Prelude Control.Monad.Omega> (1,1) `elem` runOmega (do x <- each [0..] ; y <- each [0..] ; return (x,y)) True Prelude Control.Monad.Omega>
It does breadth-first instead of depth-first search.
Note however that it's not a true monad, as it doesn't satisfy the associativity law, unless you ignore the order of the elements. The point is discussed by Spivey and Seres in their chapter in The Fun of Programming.