elem of infinite set of tuple
|
View:
New views
7 Messages
—
Rating Filter:
Alert me
|
 |
elem of infinite set of tuple
by leledumbo
::
Rate this Message:
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. |
|
|
Re: elem of infinite set of tuple
by Bugzilla from droundy@darcs.net
::
Rate this Message:
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 _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@... http://www.haskell.org/mailman/listinfo/haskell-cafe |
|
|
Re: elem of infinite set of tuple
by Abhay Parvate
::
Rate this Message:
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@...> wrote:
_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@... http://www.haskell.org/mailman/listinfo/haskell-cafe |
|
|
Re: elem of infinite set of tuple
by Dan Doel
::
Rate this Message:
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 _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@... http://www.haskell.org/mailman/listinfo/haskell-cafe |
|
|
Re: elem of infinite set of tuple
by Bugzilla from droundy@darcs.net
::
Rate this Message:
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 _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@... http://www.haskell.org/mailman/listinfo/haskell-cafe |
|
|
Re: elem of infinite set of tuple
by Ross Paterson
::
Rate this Message:
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. _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@... http://www.haskell.org/mailman/listinfo/haskell-cafe |
|
|
Re: elem of infinite set of tuple
by Henning Thielemann
::
Rate this Message:
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 _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@... http://www.haskell.org/mailman/listinfo/haskell-cafe |
| Free embeddable forum powered by Nabble | Forum Help |
