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 :) , how about we add this to
: the language?

Maybe that's just what reduce operators do in list context.

Larry

Larry Wall writes:

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<saycall, 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 writes:

5/9/06, Smylers <Smylers (AT) stripey (DOT) comwrote:

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 wrote:
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 :) , 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. 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

Gaal Yahas writes:

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.

K, 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<mapblocks and C<sayarguments 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.

K, 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

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<boolsto 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<@bitsthat 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

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<boolsto 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

Mark A. Biggar wrote:
Austin Hastings wrote:
>Gaal Yahas wrote:
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 :) , 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. 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.

, 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

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