Ken Fox wrote:
> John Porter wrote:
> > Jeremy Howard wrote:
> > > Yes, they're not identical. What I mean of course is:
> > > (..-1) == reverse(map -__ (1..));
> >
> > WHAT? So the semantics of .. are magically different in the context
> > of (..$n) so as to produce numbers in descending order?
>
No. They're in ascending order.
map {-$[0]} (1..)
is in descending order. That's way the reverse() is there.
> Both of those expressions are the infinite list (-infinity..-1). I have
> no idea how to write that properly 'cause I'm not a math guy. These
> things aren't streams (infinite queues) -- they're infinite stacks. I'm
> not sure they have a name in computer science.
>
In functional programming they're just called 'lists'!
> Somebody proposed that we have lists that are infinite in both
> directions, but I'm having trouble understanding how those would be
> useful. Anybody want to take a few minutes to teach the math-impaired
> among us?
>
'Twas me! Mathematicians don't restrict themselves to working with the
natural numbers... we like numbers less than zero too! (...and rationals,
complex numbers, etc...) Sometimes these numbers are a set, and sometimes
they're an ordered list. These lists or sets need not be finite in size (in
fact no mathematician would be caught dead discussing finite numbers ;-)
Maybe this will all make sense next Monday when PDL-Porters submit their
Numerical Perl RFCs... One of those RFCs (if I get my way!) will propose a
more general mechanism for generating lists that extends the '..' operator.
<Warning: lengthy spiel coming...>
When it comes down to it, anything you can do with a list, you can do with a
function. A list is really a mapping of the natural numbers on to some
range, and a function is a description of a mapping too (although their
domain is not restricted to natural numbers). For instance:
@a = (-2,4,10);
maps 1->-2, 2->4, 3->10. Or as a function:
$a = sub {$[0]==0 ? -2 : $[0]==1 ? 4 : $[0]==2 ? 10 : die};
or as a higher order function (with shiny new prefixes!):
$a = ^_ == 0 ? -2 : ^_ == 1 ? 4 : ^_ == 2 ? 10 : die;
TMTOWTDI! We already know finite lists are nice to have though, because they
allow more compact and intuitive notation than using functions all the time,
and they allow perl to do all kinds of optimisations. Of course, a nice side
effect of lists is that we can do stuff to all of them at once:
@b = map {$_+1} @a;
Which with a subroutine requires explicitly stating the domain by creating a
loop:
for ($i=0; $i++; $i<=2) {
$b[$i] = $a->($i) + 1;
}
The same argument is true of infinite lists:
@a = (1..:3);
might create an infinite list (1,4,7,...) if we allow slicing syntax. Then
most conveniently we can say:
@firstColOfMatrix = @Some3ColMatrix(@a);
without having to loop explicitly. That's still a list of positive integers,
of course, but we need not restrict ourselves:
@a = (-1..:-0.1); # (-1, -1.1, -1.2, ...)
and later we can reduce this neatly:
$sumOf1st10 = sum(@a, 0, 9); # Assumes sum(@list,$startIdx,$endIdx)
Many mathematical algorithms deal with many different domains of the same
infinite list while they're doing their thing. This kind of notation makes
these algorithms much easier to write.
Another side effect of lists generated by a function is that even although
they're lazily evaluated (they have to be, or it takes a little to long to
create an infinite list!), they guarantee that their results are stable.
That is, if $a[2] == 3 at one point, is will continue to equal 3 as long as
@a is not redefined. This means that generated lists can be automatically
memoized, which is a big win for many algorithms.
