Re: Scans
And here I mis-read < as <=. Perhaps I should stop "fixing", as I'm making too many errors here... On 5/10/06, Markus Laire <[EMAIL PROTECTED]> wrote: > > filter (list [<] @array) @array ==> > > first monotonically increasing run in @array > > > This seems false. @array = (1 2 2 1 2 3), if I understand you correctly, > yields (1 2 2 3). No, it yields (1, 2, 2) Correction: (1, 2) list [<] @array ==> list [<] (1, 2, 2, 1, 2, 3) ==> 1, 1 < 2, 1 < 2 < 2, 1 < 2 < 2 < 1, 1 < 2 < 2 < 1 < 2, 1 < 2 < 2 < 1 < 2 < 3, ==> Bool::True, Bool::True, Bool::True, Bool::False, Bool::False, Bool::False Correction: Bool::True, Bool::True, Bool::False, Bool::False, Bool::False, Bool::False And so filter (list [<] @array) @array would give first 3 elements of @array, i.e. (1, 2, 2) Correction: First 2 elements, i.e. (1, 2) -- Markus Laire
Re: Scans
On 5/9/06, Jonathan Scott Duff <[EMAIL PROTECTED]> wrote: On Tue, May 09, 2006 at 06:07:26PM +0300, Markus Laire wrote: > ps. Should first element of scan be 0-argument or 1-argument case. > i.e. should list([+] 1) return (0, 1) or (1) I noticed this in earlier posts and thought it odd that anyone would want to get an extra zero arg that they didn't specify. My vote would be that list([+] 1) == (1) just like [+] 1 == 1 Yes, that was an error on my part. I mis-read the example from Juerd as giving 0 arguments for first item, while it gives the "0th" argument of an array. I (now) agree that it doesn't seem to be usefull to include the 0-argument case. -- Markus Laire
Re: Scans
In the previous mail I accidentally read [<=] as [>=] On 5/10/06, Markus Laire <[EMAIL PROTECTED]> wrote: > > filter (list [<=] @array) @array ==> > > first monotonically non-decreasing run in @array > > So @array = (1 0 -1 -2 -1 -3) ==> (1, -1) is monotonically non-decreasing? This would give (1, 0, -1, -2) Correction: This would give (1) list [<=] (1, 0, -1, -2, -1, -3) ==> 1, 1 <= 0, 1 <= 0 <= -1, 1 <= 0 <= -1 <= -2, 1 <= 0 <= -1 <= -2 <= -1, 1 <= 0 <= -1 <= -2 <= -1 <= -3 ==> Bool::True, Bool::True, Bool::True, Bool::True, Bool::False, Bool::False Correction: Bool::True, Bool::False, Bool::False, Bool::False, Bool::False, Bool::False And so filter (list [<=] @array) @array would give first 4 elements of @array, i.e. (1, 0, -1, -2) Correction: It would give only first element of @array, i.e. (1) -- Markus Laire
Re: Scans
On 5/10/06, Austin Hastings <[EMAIL PROTECTED]> wrote: Mark A. Biggar wrote: > Use hyper compare ops to select what you want followed by using filter > to prune out the unwanted. > > filter gives you with scan: > > filter (list [<] @array) @array ==> > first monotonically increasing run in @array > This seems false. @array = (1 2 2 1 2 3), if I understand you correctly, yields (1 2 2 3). No, it yields (1, 2, 2) list [<] @array ==> list [<] (1, 2, 2, 1, 2, 3) ==> 1, 1 < 2, 1 < 2 < 2, 1 < 2 < 2 < 1, 1 < 2 < 2 < 1 < 2, 1 < 2 < 2 < 1 < 2 < 3, ==> Bool::True, Bool::True, Bool::True, Bool::False, Bool::False, Bool::False And so filter (list [<] @array) @array would give first 3 elements of @array, i.e. (1, 2, 2) > filter (list [<=] @array) @array ==> > first monotonically non-decreasing run in @array So @array = (1 0 -1 -2 -1 -3) ==> (1, -1) is monotonically non-decreasing? This would give (1, 0, -1, -2) list [<=] (1, 0, -1, -2, -1, -3) ==> 1, 1 <= 0, 1 <= 0 <= -1, 1 <= 0 <= -1 <= -2, 1 <= 0 <= -1 <= -2 <= -1, 1 <= 0 <= -1 <= -2 <= -1 <= -3 ==> Bool::True, Bool::True, Bool::True, Bool::True, Bool::False, Bool::False And so filter (list [<=] @array) @array would give first 4 elements of @array, i.e. (1, 0, -1, -2) -- Markus Laire
Re: Scans
Smylers wrote: Mark A. Biggar writes: Austin Hastings wrote: Gaal Yahas wrote: list [==] 0, 0, 1, 2, 2; # bool::false? # (bool::true, bool::true, bool::false, bool::false, bool::false) (And I'm with Smylers on this one: show me a useful example, please.) Well the above example does tell you where the leading prefix of equal values stops, assuming the second answer. But you still have to iterate through the list of C to get that index -- so you may as well have just iterated through the input list and examined the values till you found one that differed. I think the one thing that is redeeming scans in this case is the (my?) assumption that they are automatically lazy. The downside is that they aren't random-access, at least not in 6.0. I expect that @scan ::= list [==] @array; say @scan[12]; will have to perform all the compares, since it probably won't be smart enough to know that == doesn't accumulate. So yes, you iterate over the scan until you find whatever you're looking for. Then you stop searching. If you can't stop (because you're using some other listop) that could hurt. At the most useful, it's a clever syntax for doing a map() that can compare predecessor with present value. I think that's a far better angle than any APL clonage. But because it's a side-effect of reduce, it would have to be coded using "$b but true" to support the next operation: sub find_insert($a, $b, $new) { my $insert_here = (defined($b) ? ($a <= $new < $b) : $new < $a); return $b but $insert_here; } Then : sub list_insert($x) { &ins := &find_insert.assuming($new => $x); @.list.splice(first([&ins] @array).k, 0, $x); } It's a safe bet I've blown the syntax. :( I think I'm more enthusiastic for a pairwise traversal (map2 anyone?) than for scan. But I *know* map2 belongs in a module. :) the bit vector form of grep (maybe called filter); filter (1 0 0 1 0 1 1) (1 2 3 4 5 6 7 8) ==> (1 4 6 7) Please don't! The name 'filter' is far too useful to impose a meaning as specific as this on it. Hear, hear! Ixnay on the ilterfay. =Austin
Re: Scans
Austin Hastings wrote: I'm thinking that APL is dead for a reason. And that every language designer in the world has had a chance to pick over its dessicated bones: all the good stuff has been stolen already. So while "scans" may fall out as a potential side-effect of reduce, the real question should be "are 'scans' useful enough to justify introducing context sensitivity to the reduce operation?" Amen! Damian
Re: Scans
Mark A. Biggar wrote: Austin Hastings wrote: Gaal Yahas wrote: On Mon, May 08, 2006 at 04:02:35PM -0700, Larry Wall wrote: : I'm probably not thinking hard enough, so if anyone can come up with an : implementation please give it :) Otherwise, how about we add this to : the language? Maybe that's just what reduce operators do in list context. I love this idea and have implemented it in r10246. One question though, what should a scan for chained ops do? list [==] 0, 0, 1, 2, 2; # bool::false? # (bool::true, bool::true, bool::false, bool::false, bool::false) Keeping in mind that the scan will contain the boolean results of the comparisons, you'd be comparing 2 with "true" in the later stages of the scan. Is that what you intended, or would ~~ be more appropriate? (And I'm with Smylers on this one: show me a useful example, please.) Well the above example does tell you where the leading prefix of equal values stops, assuming the second answer. That's a long way to go... Combined with reduce it gives some interesting results: [+] list [?&] @bits ==> index of first zero in bit vector Likely to win the obfuscated Perl contest, but ...? There are other APLish operators that could be very useful in combination with reduce and scan: the bit vector form of grep (maybe called filter); filter (1 0 0 1 0 1 1) (1 2 3 4 5 6 7 8) ==> (1 4 6 7) This is really useful if your selecting out of multiple parallel arrays. Okay, this begins to approach the land of useful. If there's a faster/better/stronger way to do array or hash slices, I'm interested. But the approach above doesn't seem to be it. Use hyper compare ops to select what you want followed by using filter to prune out the unwanted. filter gives you with scan: filter (list [<] @array) @array ==> first monotonically increasing run in @array This seems false. @array = (1 2 2 1 2 3), if I understand you correctly, yields (1 2 2 3). filter (list [<=] @array) @array ==> first monotonically non-decreasing run in @array So @array = (1 0 -1 -2 -1 -3) ==> (1, -1) is monotonically non-decreasing? That was 5 minutes of thinking. I'm thinking that APL is dead for a reason. And that every language designer in the world has had a chance to pick over its dessicated bones: all the good stuff has been stolen already. So while "scans" may fall out as a potential side-effect of reduce, the real question should be "are 'scans' useful enough to justify introducing context sensitivity to the reduce operation?" =Austin
Re: Scans
Mark A. Biggar writes: > Austin Hastings wrote: > > > Gaal Yahas wrote: > > > > > list [==] 0, 0, 1, 2, 2; > > > # bool::false? > > > # (bool::true, bool::true, bool::false, bool::false, bool::false) > > > >(And I'm with Smylers on this one: show me a useful example, please.) > > Well the above example does tell you where the leading prefix of equal > values stops, assuming the second answer. But you still have to iterate through the list of C to get that index -- so you may as well have just iterated through the input list and examined the values till you found one that differed. > Combined with reduce it gives some interesting results: > > [+] list [?&] @bits ==> index of first zero in bit vector Yer what? Are you seriously suggesting that as a sane way of finding the first element of C<@bits> that contains a zero? That doesn't even short-cut (since the addition reduction can't know that once it starts adding on zeros all the remaining values are also going to be zeros). > There are other APLish operators that could be very useful in > combination with reduce and scan: The fact that there are more operators that go with these only adds to my suspicion that this field of stuff is appropriate for a module, not the core language. > the bit vector form of grep (maybe called filter); > filter (1 0 0 1 0 1 1) (1 2 3 4 5 6 7 8) ==> (1 4 6 7) Please don't! The name 'filter' is far too useful to impose a meaning as specific as this on it. Smylers
Re: Scans
Gaal Yahas writes: > On Tue, May 09, 2006 at 11:23:48AM +0100, Smylers wrote: > > > So I have the list generated by the scan. And? What do I do with > > it? I can't think of any situation in my life where I've been > > wanting such a list. > > Scans are useful when the intermediate results are interesting, as > well as when you want to cut off a stream once some threshold > condition is met. OK, we're getting closer, but that still sounds quite abstract to me. > item [+] 1 .. 10; # 10th triangular number > list [+] 1 .. 10; # 10 first triangular number > first { $_ > 42 } [+] 1 ..* # first triangular number over 42 Same question, but one level further on: why would I want the first 10 triangular numbers, or the first triangular number over 42? Sorry to keep going on like this, but I'm still struggling to see what this gets us. Is wanting to do something like that sufficiently common in real-life situations? I've seen other people ask similar questions about features such as juctions and hyperoperators (and folk were able to come up with suitable examples), but in those cases there was also response that these are features which beginners can choose to ignore. I'd have no particular objection to scans being in Perl 6 if those of us without sufficient imagination were able to just ignore them, and act like they don't exist. But if things that look like reductions sometimes turn out to be scans then I have to know about them (even if just to avoid them) anyway. And I have no problem in thinking of lots of situations where I'd find reductions handy. It slightly unnerves me that I suspect some of those would happen to be in list context -- not because I wanted a list, but because things like C blocks and C arguments are always lists. Are scans sufficiently useful that they are worth making reductions more awkward, and have a higher barrier to entry (since you now have to learn about both reductions and scans at the same time in order to be able to use only one of them). > If you have a series whose sum yields closer and closer approximations > of some value, you can use a scan to efficiently cut off once some > epsilon is reached. OK, I can see why mathematicians and engineers would want to do that. But that's a specialist field; couldn't this functionality be provided in a module? I'm unconvinced that core Perl needs features for closely approximating mathematicians any more than it needs, say, CGI parameter parsing or DBI -- they're all niches that some people use lots and others won't touch at all. Smylers
Re: Scans
On Tue, May 09, 2006 at 06:07:26PM +0300, Markus Laire wrote: > ps. Should first element of scan be 0-argument or 1-argument case. > i.e. should list([+] 1) return (0, 1) or (1) I noticed this in earlier posts and thought it odd that anyone would want to get an extra zero arg that they didn't specify. My vote would be that list([+] 1) == (1) just like [+] 1 == 1 -Scott -- Jonathan Scott Duff [EMAIL PROTECTED]
Re: Scans
Austin Hastings wrote: Gaal Yahas wrote: On Mon, May 08, 2006 at 04:02:35PM -0700, Larry Wall wrote: : I'm probably not thinking hard enough, so if anyone can come up with an : implementation please give it :) Otherwise, how about we add this to : the language? Maybe that's just what reduce operators do in list context. I love this idea and have implemented it in r10246. One question though, what should a scan for chained ops do? list [==] 0, 0, 1, 2, 2; # bool::false? # (bool::true, bool::true, bool::false, bool::false, bool::false) Keeping in mind that the scan will contain the boolean results of the comparisons, you'd be comparing 2 with "true" in the later stages of the scan. Is that what you intended, or would ~~ be more appropriate? (And I'm with Smylers on this one: show me a useful example, please.) Well the above example does tell you where the leading prefix of equal values stops, assuming the second answer. Combined with reduce it gives some interesting results: [+] list [?&] @bits ==> index of first zero in bit vector There are other APLish operators that could be very useful in combination with reduce and scan: the bit vector form of grep (maybe called filter); filter (1 0 0 1 0 1 1) (1 2 3 4 5 6 7 8) ==> (1 4 6 7) This is really useful if your selecting out of multiple parallel arrays. Use hyper compare ops to select what you want followed by using filter to prune out the unwanted. filter gives you with scan: filter (list [<] @array) @array ==> first monotonically increasing run in @array filter (list [<=] @array) @array ==> first monotonically non-decreasing run in @array That was 5 minutes of thinking. Mark Biggar -- [EMAIL PROTECTED] [EMAIL PROTECTED]
Re: Scans
Markus Laire wrote: ps. Should first element of scan be 0-argument or 1-argument case. i.e. should list([+] 1) return (0, 1) or (1) APL defines it as the later (1). -- [EMAIL PROTECTED] [EMAIL PROTECTED]
Re: Scans
Austin Hastings wrote: Gaal Yahas wrote: On Mon, May 08, 2006 at 04:02:35PM -0700, Larry Wall wrote: : I'm probably not thinking hard enough, so if anyone can come up with an : implementation please give it :) Otherwise, how about we add this to : the language? Maybe that's just what reduce operators do in list context. I love this idea and have implemented it in r10246. One question though, what should a scan for chained ops do? list [==] 0, 0, 1, 2, 2; # bool::false? # (bool::true, bool::true, bool::false, bool::false, bool::false) Keeping in mind that the scan will contain the boolean results of the comparisons, you'd be comparing 2 with "true" in the later stages of the scan. Is that what you intended, or would ~~ be more appropriate? (And I'm with Smylers on this one: show me a useful example, please.) Well the above example does tell you where the leading prefix of equal values stops, assuming the second answer. Combined with reduce it gives some interesting results: [+] list [?&] @bits ==> index of first zero in bit vector There are other APLish operators that could be very useful in combination with reduce and scan: the bit vector form of grep (maybe called filter); filter (1 0 0 1 0 1 1) (1 2 3 4 5 6 7 8) ==> (1 4 6 7) This is really useful if your selecting out of multiple parallel arrays. Use hyper compare ops to select what you want followed by using filter to prune out the unwanted. filter gives you with scan: filter (list [<] @array) @array ==> first monotonically increasing run in @array filter (list [<=] @array) @array ==> first monotonically non-decreasing run in @array That was 5 minutes of thinking. Mark Biggar -- [EMAIL PROTECTED] [EMAIL PROTECTED]
Re: Scans
On 5/9/06, Austin Hastings <[EMAIL PROTECTED]> wrote: Gaal Yahas wrote: > I love this idea and have implemented it in r10246. One question though, > what should a scan for chained ops do? > > list [==] 0, 0, 1, 2, 2; > # bool::false? > # (bool::true, bool::true, bool::false, bool::false, bool::false) Keeping in mind that the scan will contain the boolean results of the comparisons, you'd be comparing 2 with "true" in the later stages of the scan. Is that what you intended, or would ~~ be more appropriate? This code list [==] 0, 0, 1, 2, 2; would expand to [==] 0, 0 == 0, 0 == 0 == 1, 0 == 0 == 1 == 2, 0 == 0 == 1 == 2 == 2 which gives Bool::True, Bool::True, Bool::False, Bool::False, Bool::False So you don't compare 2 to "true" in any stage. ps. Should first element of scan be 0-argument or 1-argument case. i.e. should list([+] 1) return (0, 1) or (1) -- Markus Laire
Re: Scans
Gaal Yahas wrote: On Mon, May 08, 2006 at 04:02:35PM -0700, Larry Wall wrote: : I'm probably not thinking hard enough, so if anyone can come up with an : implementation please give it :) Otherwise, how about we add this to : the language? Maybe that's just what reduce operators do in list context. I love this idea and have implemented it in r10246. One question though, what should a scan for chained ops do? list [==] 0, 0, 1, 2, 2; # bool::false? # (bool::true, bool::true, bool::false, bool::false, bool::false) Keeping in mind that the scan will contain the boolean results of the comparisons, you'd be comparing 2 with "true" in the later stages of the scan. Is that what you intended, or would ~~ be more appropriate? (And I'm with Smylers on this one: show me a useful example, please.) =Austin
Re: Scans
On Tue, May 09, 2006 at 11:23:48AM +0100, Smylers wrote: > So I have the list generated by the scan. And? What do I do with it? > I can't think of any situation in my life where I've been wanting such a > list. Scans are useful when the intermediate results are interesting, as well as when you want to cut off a stream once some threshold condition is met. item [+] 1 .. 10; # 10th triangular number list [+] 1 .. 10; # 10 first triangular number first { $_ > 42 } [+] 1 ..* # first triangular number over 42 If you have a series whose sum yields closer and closer approximations of some value, you can use a scan to efficiently cut off once some epsilon is reached. -- Gaal Yahas <[EMAIL PROTECTED]> http://gaal.livejournal.com/
Re: Scans
On Mon, May 08, 2006 at 04:02:35PM -0700, Larry Wall wrote: > : I'm probably not thinking hard enough, so if anyone can come up with an > : implementation please give it :) Otherwise, how about we add this to > : the language? > > Maybe that's just what reduce operators do in list context. I love this idea and have implemented it in r10246. One question though, what should a scan for chained ops do? list [==] 0, 0, 1, 2, 2; # bool::false? # (bool::true, bool::true, bool::false, bool::false, bool::false) ? -- Gaal Yahas <[EMAIL PROTECTED]> http://gaal.livejournal.com/
Re: Scans
Markus Laire writes: > On 5/9/06, Smylers <[EMAIL PROTECTED]> wrote: > > > But this could just be because I don't (yet) grok scans. > > Here's a simple example: >[+] 1,2,3,4,5 > would return scalar 1+2+3+4+5 as a reduction and list (0, 1, 1+2, > 1+2+3, 1+2+3+4, 1+2+3+4+5) as a scan. That doesn't help. I can understand the mechanics of _what_ scans do. What I'm struggling with is _why_ they are billed as being "very useful". So I have the list generated by the scan. And? What do I do with it? I can't think of any situation in my life where I've been wanting such a list. Smylers
Re: Scans
On 5/9/06, Smylers <[EMAIL PROTECTED]> wrote: But this could just be because I don't (yet) grok scans. Here's a simple example: [+] 1,2,3,4,5 would return scalar 1+2+3+4+5 as a reduction and list (0, 1, 1+2, 1+2+3, 1+2+3+4, 1+2+3+4+5) as a scan. (0 comes from [+](), i.e. [+] with no arguments) -- Markus Laire
Re: Scans
Larry Wall writes: > On Mon, May 08, 2006 at 05:30:23PM +0300, Gaal Yahas wrote: > > : We have a very nifty reduce metaoperator. Scans are a counterpart of > : reduce that are very useful -- they are the (preferably lazy) list > : of consecutive accumulated reductions up to the final result. I'm obviously insufficiently imaginative. Please can you give a few examples of these things being very useful? > Maybe that's just what reduce operators do in list context. Instinctively I'm resistant to that, cos I can think of situations where I'd invoke reduce operators (or where I already do the Perl 5 equivalent) wanting a reduction and where the code just happens to be in list context: in a C call, or in the block of a C. Having to remember to use C<~> or C<+> to avoid inadvertently getting something complicated I don't understand sounds like the kind of thing that would trip me up. But this could just be because I don't (yet) grok scans. Smylers
Re: Scans
On Mon, May 08, 2006 at 05:30:23PM +0300, Gaal Yahas wrote: : We have a very nifty reduce metaoperator. Scans are a counterpart of : reduce that are very useful -- they are the (preferably lazy) list of : consecutive accumulated reductions up to the final result. But I can't : think of a convenient way of expressing scans in Perl 6. : : I'm probably not thinking hard enough, so if anyone can come up with an : implementation please give it :) Otherwise, how about we add this to : the language? Maybe that's just what reduce operators do in list context. Larry
Re: Scans
Gaal Yahas skribis 2006-05-08 17:58 (+0300): > (Is there special sugar to make @input be the last index when used in a > range, or did you mean ..^ ?) I meant @input.last, or probably @input.indices (or .keys?) instead of the entire range, and @input.first instead of the first 0. Juerd -- http://convolution.nl/maak_juerd_blij.html http://convolution.nl/make_juerd_happy.html http://convolution.nl/gajigu_juerd_n.html
Re: Scans
On Mon, May 08, 2006 at 04:44:51PM +0200, Juerd wrote: > To make sure I understand what you mean, not as a proposed > implementation: > > my @input = (...); > my @scan = map { [op] @input[0..$_] } [EMAIL PROTECTED]; > > Is this what you mean? > > Hm, could that be written as: > > my @scan = [op]<< @input[ 0 ..<< ([EMAIL PROTECTED]) ] Yes, except that interim results need not be recalculated. (Indeed, they are not in Haskell; implementing this feature on the .hs pugs runcore should be straightforward.) (Is there special sugar to make @input be the last index when used in a range, or did you mean ..^ ?) -- Gaal Yahas <[EMAIL PROTECTED]> http://gaal.livejournal.com/
Re: Scans
Gaal Yahas skribis 2006-05-08 17:30 (+0300): > We have a very nifty reduce metaoperator. Scans are a counterpart of > reduce that are very useful -- they are the (preferably lazy) list of > consecutive accumulated reductions up to the final result. But I can't > think of a convenient way of expressing scans in Perl 6. To make sure I understand what you mean, not as a proposed implementation: my @input = (...); my @scan = map { [op] @input[0..$_] } [EMAIL PROTECTED]; Is this what you mean? Hm, could that be written as: my @scan = [op]<< @input[ 0 ..<< ([EMAIL PROTECTED]) ] Juerd -- http://convolution.nl/maak_juerd_blij.html http://convolution.nl/make_juerd_happy.html http://convolution.nl/gajigu_juerd_n.html