[Haskell-cafe] elem of infinite set of tuple

[Ross Paterson]

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.