"Jeremy Howard" <[EMAIL PROTECTED]> writes:
> > Ariel Scolnicov wrote:
> > 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, ...".
> >
> You could say the same of:
> $someNums = grep __<-1 (1..);
> print "You'll never see me!"; # Not true! You'll see why shortly!
>
> You see, this is not a problem with (..1), or infinite lists like {(1..) .
> map -__ (..0)}, it's a problem with all semi-finite lists. If the domain
> within which the first argument to grep (in this case) can return true is
> unknown, we never know when to stop evaluating the list!
>
> But this is OK, because, as I mentioned in my last post, the argument is
> evaluated lazily. We only have to worry about the domain when we:
> 1- Reduce the list
> 2- Output the list
Let's settle for one simple case: "output the first element", when the
lazy list has a well-defined first element (e.g. when it is nonempty
and finite). If you could guarantee me that, I'd be pleased, and it's
certainly less than what you want.
But I doubt you are even able to do this (through no fault of your
own, but a fault of mathematics) for lists like (..0).
For any result of grepping (1..) (with a predicate which always
terminates, say), you can do this. If C<grep { g($_) } (1..)> is
nonempty, then it has a first element; we can find this first element
by running essentially this:
for(my $n=1; ; $n++) {
last if g($n)
}
Note that this even works if g(n) is true for infinitely many
(positive) values of n.
But the same is not true for C<grep { g($_) } (..0)>. First, in order
to have a first value for this lazy list, g(n) must be true only for
finitely many (negative) values of n (for example, (..0) certainly
doesn't have a first value!). And no amount of computation can prove
propositions of the form "g(n) is true only for 17 different values of
n" for a general g(n).
> Actually, outputting the list isn't so bad. We can assume that the
> programmer knows what they're doing, and that they'll signal a break in some
> way when they're ready.
Note that you cannot even output the list (..0), since it has no
beginning (it does have an end, but I hope you don't call "0, -1, -2,
..." the result of outputting (..0)!).
[...]
> However, the point is that there are no challenges introduced by (..1) that
> aren't in (1..), and that there are no challenges in (1..) . (..0) that
> aren't in (..1). So if Damian's RFCs on lazy evaluation and reduction deal
> with semi-finite lists OK, then (..) will be just as doable as (1..).
See above. Lazy lists are defined by these 2 requirements:
(1) An effective procedure to compute the *first* element.
(2) An effective procedure to produce a lazy list of the remaining
elements, or signal that that list is empty.
(..0) doesn't satisfy even condition (1).
--
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
