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..] ] If I try to query elemOf (1,1), the program keeps searching and searching but it never makes it. But if I query elemOf (0,1) (or anything as long as the first element is 0), it can find it easily. I wonder how it's handled.
From my point of view, instead of starting from (1,0), the program starts from (0,0), which will never finish since the limit of the second element is infinite. -- View this message in context: http://www.nabble.com/elem-of-infinite-set-of-tuple-tp17272802p17272802.html Sent from the Haskell - Haskell-Cafe mailing list archive at Nabble.com.
On Fri, May 16, 2008 at 04:42:31AM -0700, 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..] ]
If I try to query elemOf (1,1), the program keeps searching and searching but it never makes it. But if I query elemOf (0,1) (or anything as long as the first element is 0), it can find it easily. I wonder how it's handled.
From my point of view, instead of starting from (1,0), the program starts from (0,0), which will never finish since the limit of the second element is infinite.
Didn't you just answer your own question? -- David Roundy Department of Physics Oregon State University
It's not exactly a question of Haskell's behaviour. The list [ (a,b) | a <-
[0..], b <- [0..] ]
is such that apart from pairs starting with zero, no other pair is
associated with a finite index. In other words, [ (a,b) | a <- [0..], b <-
[0..] ] is not a correct 'enumeration' of all pairs of nonnegative integers.
You need to reorder them if you need a finite index associated with every
pair.
On Fri, May 16, 2008 at 5:12 PM, leledumbo
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..] ]
If I try to query elemOf (1,1), the program keeps searching and searching but it never makes it. But if I query elemOf (0,1) (or anything as long as the first element is 0), it can find it easily. I wonder how it's handled.
From my point of view, instead of starting from (1,0), the program starts from (0,0), which will never finish since the limit of the second element is infinite. -- View this message in context: http://www.nabble.com/elem-of-infinite-set-of-tuple-tp17272802p17272802.html Sent from the Haskell - Haskell-Cafe mailing list archive at Nabble.com.
_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
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. -- Dan
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.
You could also just use [ (b,a-b) | a <- [0..], b <- [0..a]] David
On Fri, 16 May 2008, David Roundy wrote:
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.
You could also just use [ (b,a-b) | a <- [0..], b <- [0..a]]
I wonder whether Georg Cantor could imagine that his diagonalization method would be practically applied some day. http://de.wikipedia.org/wiki/Cantor-Diagonalisierung
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.
participants (6)
-
Abhay Parvate -
Dan Doel -
David Roundy -
Henning Thielemann -
leledumbo -
Ross Paterson