Scans
Gaal Yahas
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?
--
Gaal Yahas <ga...@forum2.org>
http://gaal.livejournal.com/
Juerd
> 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..$_] } 0..@input;
Is this what you mean?
Hm, could that be written as:
my @scan = [op]<< @input[ 0 ..<< (0..@input) ]
Juerd
--
http://convolution.nl/maak_juerd_blij.html
http://convolution.nl/make_juerd_happy.html
http://convolution.nl/gajigu_juerd_n.html
Gaal Yahas
> To make sure I understand what you mean, not as a proposed
> implementation:
>
> my @input = (...);
> my @scan = map { [op] @input[0..$_] } 0..@input;
>
> Is this what you mean?
>
> Hm, could that be written as:
>
> my @scan = [op]<< @input[ 0 ..<< (0..@input) ]
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 ..^ ?)
Juerd
> (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.
Larry Wall
: 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
Smylers
> 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<say> call, or in the block of a C<map>. 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
Markus Laire
> 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
Smylers
> On 5/9/06, Smylers <Smy...@stripey.com> 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
Gaal Yahas
> : 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
> 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.
Austin Hastings
> 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)
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
Markus Laire
> 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
Mark A. Biggar
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
Mark A. Biggar
> 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).
Mark A. Biggar
Well the above example does tell you where the leading prefix of equal
Jonathan Scott Duff
> 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
du...@pobox.com
Smylers
> 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<map> blocks and C<say> 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
Smylers
> 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<bools> 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
Austin Hastings
> 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.
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
Damian Conway
> 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
Austin Hastings
> 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<bools> 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
Markus Laire
> 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
Markus Laire
> 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
Markus Laire
On 5/10/06, Markus Laire <mal...@gmail.com> 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
Markus Laire
Perhaps I should stop "fixing", as I'm making too many errors here...
On 5/10/06, Markus Laire <mal...@gmail.com> 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