Re: Infinite lists (was Re: RFC 24 (v1) Semi-finite (lazy) lists)
John Porter wrote: > Jeremy Howard wrote: > > The reason that having (1..) implies having (..-1) is that if you allow > > (1..), then this is a valid construct: > > > > @dot_dot_neg_one = reverse (map {-$_} (1..)); > > > > which is identical to (..-1)! > > No, NOT identical. The same set of numbers, yes, but generated in > the opposite order. (..-1) should generate -INF first, but obviously > it can't do that. (..$n) is an impossible construct, and should be > a fatal error -- presuming it even gets past the lexer... > Well, maybe... If you think the idea of 'generation order' is meaningful. I would have thought that it should look like all the elements are generated together--since I don't think we want to confuse lists and streams. Anyhow, maybe this is a moot point. Damian's recanted his RFC, and I'm still trying to decide whether this is important enough to finish off a redraft of it that I started...
Re: Infinite lists (was Re: RFC 24 (v1) Semi-finite (lazy) lists)
Jeremy Howard wrote: > The reason that having (1..) implies having (..-1) is that if you allow > (1..), then this is a valid construct: > > @dot_dot_neg_one = reverse (map {-$_} (1..)); > > which is identical to (..-1)! No, NOT identical. The same set of numbers, yes, but generated in the opposite order. (..-1) should generate -INF first, but obviously it can't do that. (..$n) is an impossible construct, and should be a fatal error -- presuming it even gets past the lexer... -- John Porter
Re: Infinite lists (was Re: RFC 24 (v1) Semi-finite (lazy) lists)
> > I'm thinking of recanting the whole RFC! :-) > > <*checking etymology*> hmmm . . . "recant" . . . "recant" . . . > doesn't that mean to sing the whole thing over again? Literally: "to sing a different tune". :-) > Seems to me that while putting hooks in the core to allow this sort > of thing might be worthwhile, infinite lists are not likely to be > commonly used and so probably should go into a module. Agreed. I hereby bequeath the rewrite to someone else. Damian
Re: Infinite lists (was Re: RFC 24 (v1) Semi-finite (lazy) lists)
Thus it was written in the epistle of Damian Conway, >> I'm looking forward to the upcoming writeup :-). > > I'm thinking of recanting the whole RFC! :-) <*checking etymology*> hmmm . . . "recant" . . . "recant" . . . doesn't that mean to sing the whole thing over again? :-), Ted P.S. Seems to me that while putting hooks in the core to allow this sort of thing might be worthwhile, infinite lists are not likely to be commonly used and so probably should go into a module. -- Ted Ashton ([EMAIL PROTECTED]), Info Sys, Southern Adventist University == You know that I write slowly. This is chiefly because I am never satisfied until I have said as much as possible in a few words, and writing briefly takes far more time than writing at length. -- Gauss, Karl Friedrich (1777-1855) == Deep thoughts to be found at http://www.southern.edu/~ashted
Re: Infinite lists (was Re: RFC 24 (v1) Semi-finite (lazy) lists)
> I'm looking forward to the upcoming writeup :-). I'm thinking of recanting the whole RFC! :-) Damian
Re: Infinite lists (was Re: RFC 24 (v1) Semi-finite (lazy) lists)
Thus it was written in the epistle of Jeremy Howard, > The reason that having (1..) implies having (..-1) is that if you allow > (1..), then this is a valid construct: > > @dot_dot_neg_one = reverse (map {-$_} (1..)); > > which is identical to (..-1)! So scrapping (..-1) doesn't actually win you > anything, in terms of avoiding 'impossible loops'. > > The only way around all this, IMO, is to require that the domain of indexes > of an infinite loop be specified before the list is output in any way. > 'Output' includes reduction of the list (see RFC 76). The domain could be > specified explicitly, or could in some cases be derived by Perl implicitly > from the context of the expression. I'm looking forward to the upcoming writeup :-). Ted -- Ted Ashton ([EMAIL PROTECTED]), Info Sys, Southern Adventist University == If others would but reflect on mathematical truths as deeply and as continuously as I have, they would make my discoveries. -- Gauss, Karl Friedrich (1777-1855) == Deep thoughts to be found at http://www.southern.edu/~ashted
Re: Infinite lists (was Re: RFC 24 (v1) Semi-finite (lazy) lists)
Ted Ashton wrote: > I understand very well the concern. I, for one, don't agree that having > (1..) in the language implies that having (..-1) is possible (though it does > make sense to me that having (1..) and (..-1) would imply having (..)). After > all, if I were to write > > for (1..) { > print; > } > > I would get an infinite loop, but one which was doing something, whereas > > for (..-1) { > print; > } > The reason that having (1..) implies having (..-1) is that if you allow (1..), then this is a valid construct: @dot_dot_neg_one = reverse (map {-$_} (1..)); which is identical to (..-1)! So scrapping (..-1) doesn't actually win you anything, in terms of avoiding 'impossible loops'. The only way around all this, IMO, is to require that the domain of indexes of an infinite loop be specified before the list is output in any way. 'Output' includes reduction of the list (see RFC 76). The domain could be specified explicitly, or could in some cases be derived by Perl implicitly from the context of the expression.
Re: Infinite lists (was Re: RFC 24 (v1) Semi-finite (lazy) lists)
Ted Ashton wrote: > Thus it was written in the epistle of John Porter, > > Ken Fox wrote: > > > > > > 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. > > > > O.k., here's the basic question. (If someone has already answered this, > > I didn't find it satisfactorily comprehensible. Assume I'm an idiot.) > > > > What would be the output of the following program: > > > > $\ = "\n"; > > $i = 0; > > for ( .. -1 ) { > > $i++; > > last if $i > 2; > > print > > } > > > > If the answer is (as I suspect), "This never prints anything; it goes > > into an infinite loop just trying to generate the first number", then > > the proposal is absurd and should be scrapped. > > By my understanding (which is definitely not very thorough), the output would > be a run-time error. That's my understanding too. I'm trying to pull together a more complete proposal that describes under what conditions a list can or can not be used without specifying its domain (amongst other things). Bear with me for a day or two...
Re: Infinite lists (was Re: RFC 24 (v1) Semi-finite (lazy) lists)
Tangentialy, can I suggest that a nicer synthax might be -Inf..-1 / 1..Inf, etc. Assuming that we end up supporting full IEEE floats, this becomes the "obvious" synthax, and I find C<(-Inf..Inf)> to be far more clear then C<(..)>. We've got plenty of puncuation already, thank you very much. Also, can someone please suggest a reasonable implementation of (-Inf...-1)? If not, can I suggest that we require that if one of the arguments to (list) .. s +/-infinity, it be the second one, and additionaly say that a..b is the list , a+1, a+2, ... b if b>a, and a, a-1, a-2, ... b if a>b. This would allow the full expressiveness of both (-inf..0) and (0..inf) without ever having an infinite starting point to a list. (If a..b where a==b, then we get the list containing only a.) In any case, (-inf...-1) would "obviously" either: begin with the smallest negitive integer representable, or begin with the IEEE -inf. If it begins with the IEEE -inf, then it has to continue with an infinite number of -infs, since -inf+1=-inf (a rule of IEEE arithmitic). Ergo, it is useless to begin at -inf unless perl6 becomes _very_ good at finding out what you "really" meant. OTOH, having it begin with the smallest non-(negitive)infinite value means that it becomes non-infinite, IE scalar((-inf..0)) != inf. This is obviously a Bad Thing. Also, if bignums are intergrated (as has been proposed), then there is no smallest representable integer. (This assumes that the float synthax will be extended to include "NaN" and "Inf" as valid floating-point numbers. (This does take away from non-reserved namespace.) Has this been proposed yet?) -=- James Mastros, In slightly over his head.
Re: Infinite lists (was Re: RFC 24 (v1) Semi-finite (lazy) lists)
John Porter replied to what > Ted Ashton wrote: > > John Porter: > > > > > > What would be the output of the following program: > > > > > > $\ = "\n"; > > > $i = 0; > > > for ( .. -1 ) { > > > $i++; > > > last if $i > 2; > > > print > > > } > > > > > > If the answer is (as I suspect), "This never prints anything; it goes > > > into an infinite loop just trying to generate the first number", then > > > the proposal is absurd and should be scrapped. > > > > By my understanding (which is definitely not very thorough), the output would > > be a run-time error. > > What error message? "Program never halts!" ??? :-). I don't know, really. This proposal, while interesting to me, isn't mine and is pretty much a new thought. My guess would be that the actual list implementation would be to not unroll anything until it was needed and so the print or the for would notice that the output is still based on "coming from infinity" and would die. I understand very well the concern. I, for one, don't agree that having (1..) in the language implies that having (..-1) is possible (though it does make sense to me that having (1..) and (..-1) would imply having (..)). After all, if I were to write for (1..) { print; } I would get an infinite loop, but one which was doing something, whereas for (..-1) { print; } would either have to error out, count backwards from -1 or go into an infinite loop trying to find the beginning. Perhaps one of the proponents can enlighten us. After all, even mathematical induction cannot generate all the elements of (..-1) unless it starts at -1 and goes backward. Ted -- Ted Ashton ([EMAIL PROTECTED]), Info Sys, Southern Adventist University == Whereas at the outset geometry is reported to have concerned herself with the measurement of muddy land, she now handles celestial as well as terrestrial problems: she has extended her domain to the furthest bounds of space. -- Frankland, W.B. == Deep thoughts to be found at http://www.southern.edu/~ashted
Re: Infinite lists (was Re: RFC 24 (v1) Semi-finite (lazy) lists)
Ted Ashton wrote: > John Porter: > > > > What would be the output of the following program: > > > > $\ = "\n"; > > $i = 0; > > for ( .. -1 ) { > > $i++; > > last if $i > 2; > > print > > } > > > > If the answer is (as I suspect), "This never prints anything; it goes > > into an infinite loop just trying to generate the first number", then > > the proposal is absurd and should be scrapped. > > By my understanding (which is definitely not very thorough), the output would > be a run-time error. What error message? "Program never halts!" ??? -- John Porter
Re: Infinite lists (was Re: RFC 24 (v1) Semi-finite (lazy) lists)
Thus it was written in the epistle of John Porter, > Ken Fox wrote: > > > > 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. > > O.k., here's the basic question. (If someone has already answered this, > I didn't find it satisfactorily comprehensible. Assume I'm an idiot.) > > What would be the output of the following program: > > $\ = "\n"; > $i = 0; > for ( .. -1 ) { > $i++; > last if $i > 2; > print > } > > If the answer is (as I suspect), "This never prints anything; it goes > into an infinite loop just trying to generate the first number", then > the proposal is absurd and should be scrapped. By my understanding (which is definitely not very thorough), the output would be a run-time error. And I think that $\ = "\n"; $i = 0; for ( .. -1 ) { next unless $_ > -10; $i++; last if $i > 2; print } is supposed to print -9 -8 How it would know to do that is beyond my ken, but I believe that is what it is expected to do. Ted -- Ted Ashton ([EMAIL PROTECTED]), Info Sys, Southern Adventist University == Leibniz never married; he had considered it at the age of fifty; but the person he had in mind asked for time to reflect. This gave Leibniz time to reflect, too, and so he never married. -- Fontenelle, Bernard Le Bovier (1657-1757) == Deep thoughts to be found at http://www.southern.edu/~ashted
Re: Infinite lists (was Re: RFC 24 (v1) Semi-finite (lazy) lists)
Ken Fox wrote: > > 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. O.k., here's the basic question. (If someone has already answered this, I didn't find it satisfactorily comprehensible. Assume I'm an idiot.) What would be the output of the following program: $\ = "\n"; $i = 0; for ( .. -1 ) { $i++; last if $i > 2; print } If the answer is (as I suspect), "This never prints anything; it goes into an infinite loop just trying to generate the first number", then the proposal is absurd and should be scrapped. -- John Porter
Re: Infinite lists (was Re: RFC 24 (v1) Semi-finite (lazy) lists)
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. 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.
Re: Infinite lists (was Re: RFC 24 (v1) Semi-finite (lazy) lists)
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? 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. 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? - Ken
Re: Infinite lists (was Re: RFC 24 (v1) Semi-finite (lazy) lists)
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? I don't think so. -- John Porter
Re: Infinite lists (was Re: RFC 24 (v1) Semi-finite (lazy) lists)
Damian Conway sent the following bits through the ether: > Rather than continue to argue the details, why don't people post some > examples of code where they feel these lazy lists might be useful, and > let's see if there aren't already good alternatives. It should be noted that "infinite" lazily-evaluated lists can be used in Perl 5 in a perlish way with careful use of Tie::Array and closures. I've got an example of this in my poorly-coded Functional module[1], which allows things like: take(10, filter("prime", integers)) [yes, that is perl ;-] ... (which is done lazily) Anything to make this easier to do in Perl 6 is welcomed ;-) Leon [1] http://www.astray.com/Functional/ -- Leon Brocard.http://www.astray.com/ yapc::Europe - September 22-24 London - http://yapc.org/Europe/ ... Error 404: .signature generator ran out of tuits
Re: Infinite lists (was Re: RFC 24 (v1) Semi-finite (lazy) lists)
> > Another win is in evaluation of lists constructed by generator functions: > > # ($start: f(__): $end) == ($start, f($start), f(f($start)), ...) > > @powersOf2 = (1:__*2:); # (1, 2, 4, 8, ...) > > @first10PowersOf2 = @powersOf2[0..9]; # Calculates 1st 10 powers of 2 > > # ...interesting manipulation of @first10PowersOf2... > > @first20PowersOf2 = @powersOf2[0..19] # Calculates 2nd 10 powers of 2 (1st > > 10 are already computed!) > > This is another straightforward "forwards list"; it has the order type > of (1..), not of (..-1). > > Please post examples of places where "generalised lists" of other > order types are useful. > OK, give me a moment. I'm writing an RFC for list generators with some of the PDL folk, and I'll make sure there's a "backwards list" example in there. It's no big deal though, I don't mind writing: reverse (map {-$_} (1..)); if I have too. > > <...> > > MJD has a perl5 package which does memoization; this is exactly what > you want. > Yes, very nice it is too: http://www.plover.com/~mjd/perl/MiniMemoize/memoize.html http://www.plover.com/~mjd/perl/Memoize/ There seems to be an opportunity to integrate generators, iterators, memoizaion and lists nicely, with very little new syntax. This is what I'm trying to investigate here. Also, perl might be able to do some optimisations for us (such as the 'Orcish maneuver') if it knew about this stuff.
Re: Infinite lists (was Re: RFC 24 (v1) Semi-finite (lazy) lists)
"Jeremy Howard" <[EMAIL PROTECTED]> writes: > Damian Conway wrote: [...] > > Personally, I intend only to update the RFC to include the *possibility* > > of (..$x) and (..). I'm reasonably sure Larry will kill the whole thing > > -- I think I might too, were I in his place ;-) > > > Now don't encourage its death already! Still, I'm glad you're prepared to > keep it open. Please somebody post some sane semantics for lazy "generalised lists" with any (computable) countable order type. That way lies madness (and no applications that I can think of). > > > Rather than continue to argue the details, why don't people post some > > examples of code where they feel these lazy lists might be useful, and > > let's see if there aren't already good alternatives. > > > OK, you're on. But infinite lists (can I say that?... 'semi-finite' is a bit > weird) are one part of a bigger picture, so let me show you some code that > also incorporates higher-order functions, and an extension to Christian > Soeller's upcoming RFC on notation for slicing. > > @matrix = (1,3,4,2,6,7); # actually a flattened version of > [[1,3,4],[2,6,7]] > @column1of3 = (1:3:); # Creates an infinite list (1,4,7,...) > print sum(@matrix[@column1of3]); # Prints 3 > @matrix2 = readReallyBig3ColumnMatrixFromSomewhere(); > $column1Sum = sum(@matrix2[@column1of3]); # Handy, no need to redefine our > slice! This is a straightforward "forwards list"; it has the order type of (1..), not of (..-1). [...] > Another win is in evaluation of lists constructed by generator functions: > # ($start: f(__): $end) == ($start, f($start), f(f($start)), ...) > @powersOf2 = (1:__*2:); # (1, 2, 4, 8, ...) > @first10PowersOf2 = @powersOf2[0..9]; # Calculates 1st 10 powers of 2 > # ...interesting manipulation of @first10PowersOf2... > @first20PowersOf2 = @powersOf2[0..19] # Calculates 2nd 10 powers of 2 (1st > 10 are already computed!) This is another straightforward "forwards list"; it has the order type of (1..), not of (..-1). Please post examples of places where "generalised lists" of other order types are useful. > The real difference between an infinite list and a function with a domain of > the integers (other than notation) is that an infinite list is a guarantee > of stability. If we've already calculated @powersOf2[9], we don't have to do > it again when we next want it. The same is not true of 2^__, since perl > can't know that it returns the same result for every evaluation (for > instance, what if it was <>^__ ?) > > You could argue that we could achieve the same with an attribute of a sub, > such as 'stable'. This would guarantee that this function returns the same > result each time it's called with the same arguments. Then perl would be > smart enough to cache the result of calls to this sub to avoid recalculating > it again later. Personally, however, I find this approach less intuitive. MJD has a perl5 package which does memoization; this is exactly what you want. -- 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-7658555http://3w.compugen.co.il/~ariels
Re: Infinite lists (was Re: RFC 24 (v1) Semi-finite (lazy) lists)
Damian Conway wrote: > I think I opened a bigger can of worms than I intended :-) Yes, sorry about the overload of email you must of got from me on this, this morning ;-) > > As MJD as pointed out to me in private email, if we are serious > about this feature, we probably want to go the whole hog and > look at Haskell's notion of list comprehensions. See > > http://www.haskell.org/tutorial/goodies.html > Exactly right. Haskell provides some great ideas, although there's more perlish ways of thinking about it (give me a moment, I'll get back to them...) > Personally, I intend only to update the RFC to include the *possibility* > of (..$x) and (..). I'm reasonably sure Larry will kill the whole thing > -- I think I might too, were I in his place ;-) > Now don't encourage its death already! Still, I'm glad you're prepared to keep it open. > Rather than continue to argue the details, why don't people post some > examples of code where they feel these lazy lists might be useful, and > let's see if there aren't already good alternatives. > OK, you're on. But infinite lists (can I say that?... 'semi-finite' is a bit weird) are one part of a bigger picture, so let me show you some code that also incorporates higher-order functions, and an extension to Christian Soeller's upcoming RFC on notation for slicing. @matrix = (1,3,4,2,6,7); # actually a flattened version of [[1,3,4],[2,6,7]] @column1of3 = (1:3:); # Creates an infinite list (1,4,7,...) print sum(@matrix[@column1of3]); # Prints 3 @matrix2 = readReallyBig3ColumnMatrixFromSomewhere(); $column1Sum = sum(@matrix2[@column1of3]); # Handy, no need to redefine our slice! So, it provides some nice slicing notation. Note that more complex slicing, masking, and indirection across n-dimensional tensors would make the win of not having to respecify the indexes more substantial. But I'm trying to keep the examples simple here... Another win is in evaluation of lists constructed by generator functions: # ($start: f(__): $end) == ($start, f($start), f(f($start)), ...) @powersOf2 = (1:__*2:); # (1, 2, 4, 8, ...) @first10PowersOf2 = @powersOf2[0..9]; # Calculates 1st 10 powers of 2 # ...interesting manipulation of @first10PowersOf2... @first20PowersOf2 = @powersOf2[0..19] # Calculates 2nd 10 powers of 2 (1st 10 are already computed!) The real difference between an infinite list and a function with a domain of the integers (other than notation) is that an infinite list is a guarantee of stability. If we've already calculated @powersOf2[9], we don't have to do it again when we next want it. The same is not true of 2^__, since perl can't know that it returns the same result for every evaluation (for instance, what if it was <>^__ ?) You could argue that we could achieve the same with an attribute of a sub, such as 'stable'. This would guarantee that this function returns the same result each time it's called with the same arguments. Then perl would be smart enough to cache the result of calls to this sub to avoid recalculating it again later. Personally, however, I find this approach less intuitive.
Re: Infinite lists (was Re: RFC 24 (v1) Semi-finite (lazy) lists)
> (Note that I'm keeping the ':' notation, because then it's clear that we're > talking about a generation rule, not an upper bound). Now I write it like > this, wouldn't it be nice if we could also say: > (1..:f(__)) == apply(f(__), (1..); # But I digress! > Correction (sorry). This should be: (1..:f()) == (1) . map {apply(f(__), (1..$_))} (1..); Anyway, just ignore this nomenclature for a moment. Christian Soeller has got an RFC coming up on slicing semantics from which I've developed some better ideas on creating generating functions. I'll post these as replies to that RFC when it appears.
Re: Infinite lists (was Re: RFC 24 (v1) Semi-finite (lazy) lists)
I think I opened a bigger can of worms than I intended :-) As MJD as pointed out to me in private email, if we are serious about this feature, we probably want to go the whole hog and look at Haskell's notion of list comprehensions. See http://www.haskell.org/tutorial/goodies.html specifically, section 2.4.1. NOTE: MJD didn't *support* any of this, he merely pointed it out. Personally, I intend only to update the RFC to include the *possibility* of (..$x) and (..). I'm reasonably sure Larry will kill the whole thing -- I think I might too, were I in his place ;-) Rather than continue to argue the details, why don't people post some examples of code where they feel these lazy lists might be useful, and let's see if there aren't already good alternatives. Damian
Re: Infinite lists (was Re: RFC 24 (v1) Semi-finite (lazy) lists)
Ken Fox wrote: > Jeremy Howard wrote: > > (..-1) == map -__ (1..); > > That really confuses me. If the sequence (-4..-1) is (-4, -3, > -2, -1) then I don't see how your semantics are consistent. I'll > admit (reverse map -__ (1..)) is the same as (..-1) but reverse > on a stream is undefined. (It should be a run-time error.) > Yes, they're not identical. What I mean of course is: (..-1) == reverse(map -__ (1..)); But my point is that the programmer shouldn't have to bother with this detail. If you write (..-1) perl knows what you mean. > Streams must have a head. Infinite sequences in general don't need > a head, but streams IMHO aren't general infinite sequences. > I know MJD talked of streams and infinite lists as being interchangable concepts, but the notion that @list = ($head, promise()) is just one potential implementation. We _can_not_ actually use an infinite (or semi-finite) list until we reduce it (through filtering [eg grep], or mathematical combination [eg sum], or some combination). We can only reduce an infinite list under one of the following restrictions: 1- We know the domain under which the predicate used in the filter is true, or 2- We know a mathematical 'short-cut' such as 'sum of a geometric series = a/(1-r)' There is no general way of finding a 'short-cut' for reduce(f(__,__), @a), so we can't expect perl to deal with (2) for us. Therefore (1) is the only restriction we can use, and therefore: * We can not use an infinite list until we define a finite domain of its indexes. We can define this domain through some kind of 'stopping criteria'. Possible criteria types include: - Define the range of the indexes to test - Define the number of items to return - Define the time to search for. If you accept that we need to define a domain to reduce a list, then you can see that we can usefully talk of reverse(map -__ (1..)), because reverse() is evaluated lazily and can be applied once the finite domain is known. Note that under my definition of what you can do to a list (you must reduce it before you output it), the following is not valid perl: print (1..); # Error, attempt to output infinite list You could argue that, procedurally speaking, this has some meaning because you can signal to perl when you want it to stop outputting. But this argument comes from thinking of (1..) as a stream, which it's not, it's a list. > One thing that would make sequences composed with .. more useful > would be to allow the right hand side to be a function of one > argument. Then the set of all negative numbers is (-1..__-1) which > is the same as map -__ (1..). The set of all integer powers of two > is (1..__*2). (But map __*2 (1..) is the set of all positive even > numbers.) Another cool sequence is (1..__*-1+1) which alternates > (1, 0, 1, 0, 1, ...). (Damian probably already thought of this > though. I should go read RFC 24.) > I certainly think it would be nice to say: (1..:3) where ':3' defines a step size. But then I guess you're saying this generalises to: (i0..:f(__)) == i0, f(i0), f(f(i0), ... (Note that I'm keeping the ':' notation, because then it's clear that we're talking about a generation rule, not an upper bound). Now I write it like this, wouldn't it be nice if we could also say: (1..:f(__)) == apply(f(__), (1..); # But I digress! Yes, that would be pretty cool.
Re: Infinite lists (was Re: RFC 24 (v1) Semi-finite (lazy) lists)
Jeremy Howard wrote: > (..-1) == map -__ (1..); That really confuses me. If the sequence (-4..-1) is (-4, -3, -2, -1) then I don't see how your semantics are consistent. I'll admit (reverse map -__ (1..)) is the same as (..-1) but reverse on a stream is undefined. (It should be a run-time error.) Streams must have a head. Infinite sequences in general don't need a head, but streams IMHO aren't general infinite sequences. One thing that would make sequences composed with .. more useful would be to allow the right hand side to be a function of one argument. Then the set of all negative numbers is (-1..__-1) which is the same as map -__ (1..). The set of all integer powers of two is (1..__*2). (But map __*2 (1..) is the set of all positive even numbers.) Another cool sequence is (1..__*-1+1) which alternates (1, 0, 1, 0, 1, ...). (Damian probably already thought of this though. I should go read RFC 24.) - Ken