"Jeremy Howard" <[EMAIL PROTECTED]> writes:
> Ariel Scolnicov wrote:
> > <...infinite lists...>
> > This (and your preceeding messages on the subject) is unfortunately
> > not possible to do in a clean manner; for that matter, neither is the
> > (..0) proposal. The I<order> in which results are produced depends on
> > the order in which you generate the elements of (..). Since there's
> > no universally "good" order of the integers (do you take
> > 0,-1,+1,-2,+2,...; or maybe 0, -1,-2, 1,2,3, -3,-4,-5,-6, 4,5,6,7,8;
> > or any other order), there's no way `grep' can generate the results in
> > the correct order. But this iterator B<is> an iterator; in
> > particular, you I<expect> a well-defined order.
>
> Intuitively, I _do_ expect a well-defined order. Something that just returns
> a set is still somewhat useful, but I would like to argue that in fact we
> _can_ specify the types of list I'm proposing _and_ have our ordering. Let
> me see if I can convince you...
> >
> > But as soon as you're specifying some well-ordering of the integers,
> > you might as well use C<@ints = map {well_order $_} (1..)>, where
> > well_order is a bijection of the natural numbers onto the integeers.
> > Note that the ordering is different than ...,-2,-1,0,1,2,...
> >
> Yes, this would be a real pain. But what if we had
> @ints = (1..) . map -__ (0..);
> Then, we have all the integers... And then perl just needs to know that (..)
> and friends need a tuple, and that the second part of the tuple need to be
> reversed as soon as we need order. Eventually, infinite lists need criteria
> to become finite lists (otherwise we can't do anything useful with them!),
> so at this point perl can generate the correct order.
No, this doesn't work. (I always knew my Set Theory classes would
find real-life application!) The problem is that 0 never appears in
your list! (And the problem with my suggestion was that well-ordering
is not a sufficient demand of lists; they must have the same ordinal
type as the natural numbers, i.e. fulfill the Peano axioms).
Consider C<grep {$_ <= 0} (1..) . (map {-$_} (0..))>. Clearly, this
"should" generate the "list" C<(..0)>. But it doesn't! Here's what
really happens: Perl says to itself "1 is not nonpositive, 2 is not
nonpositive, 3 is not nonpositive, ..."; it B<never> reaches the point
where it starts saying "0 is nonpositive, -1 is nonpositive, ...".
In other words, if we try to C<for (...) { print "$_\n"}> on the above
snippet, we get the equivalent of this Perl program:
for(my $n=1; ; $n++) {
print "$n\n" if $n <= 0
}
for(my $n=0; ; $n--) {
print "$n\n" if $n <= 0
}
Since the first loop is an infinite loop which never prints anything,
nothing is ever printed.
> > Similarly, the only useful meaning of C<@negs = (..-1)> would simply
> > be C<@negs = map {-$_} (1..)>, and the ordering of the result is again
> > "wrong".
> >
> Yes, but perl knows that we said (..-1), not map -__ (1..), so it does what
> we mean as soon as we're ready to use our list in a finite context.
What B<do> we mean? I can (fairly easily) code a function p(n) for
which C<grep { p($_) } (..-1)> will be a *finite* list, so presumably
you need to generate it in ascending order. But the smallest
(i.e. first, in the ordering ... < -2 < -1 < 0) element is of the list
is uncomputable.
So it can never work.
> Note that doing this effectively requires that functions on infinite lists
> be evaluated lazily. But this is true of (1..) too.
Here the situation is different. If C<grep { p($_) } (1..)> has at
least 17 elements, then I can effectively find those 17 elements I<in
the correct order>. For any other order type, this is not true.
--
Ariel Scolnicov |"GCAAGAATTGAACTGTAG" | [EMAIL PROTECTED]
Compugen Ltd. |Tel: +972-2-6795059 (Jerusalem) \ We recycle all our Hz
72 Pinhas Rosen St. |Tel: +972-3-7658514 (Main office)`---------------------
Tel-Aviv 69512, ISRAEL |Fax: +972-3-7658555 http://3w.compugen.co.il/~ariels
