headers
leledumbo | 16 May 13:41

elem of infinite set of tuple


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.
Permalink | Reply |
headers
David Roundy | 16 May 13:49
Favicon
Gravatar

Re: elem of infinite set of tuple

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
Permalink | Reply |
headers
Abhay Parvate | 16 May 13:49

Re: elem of infinite set of tuple

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 <leledumbo_cool <at> yahoo.co.id> 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.
--
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 <at> haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe <at> haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Permalink | Reply |
headers
Dan Doel | 16 May 13:58

Re: elem of infinite set of tuple

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
Permalink | Reply |
headers
David Roundy | 16 May 14:02
Favicon
Gravatar

Re: elem of infinite set of tuple

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
Permalink | Reply |
headers
Henning Thielemann | 16 May 15:23

Re: elem of infinite set of tuple


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
Permalink | Reply |
headers
Ross Paterson | 16 May 14:29
Favicon

Re: elem of infinite set of tuple

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.
Permalink | Reply |

Gmane