How does a triangular reduction on the comma operator know to make a list of all lists?

Question

In Perl 6, doing a triangular reduction on the comma operator produces a list of lists, each of which adds one successive element from the input list:

> [\,] 1..5
((1) (1 2) (1 2 3) (1 2 3 4) (1 2 3 4 5))

Pretty nice! But recently I wondered just how it works the way it does.

If op is an arbitrary operator, [op] @list is supposed to be the same as @list[0] op @list[1] op ... op @list[*-1]. As I understand it, [\op] is then supposed to be a list of all of the intermediate values. But it seems that that should mean that [\op] @list should evaluate to (@list[0], @list[0] op @list[1], @list[0] op @list[1] op @list[2], ...). In my original case where op is ,, the first element of the output list should then just be @list[0], but it isn't; it's a singleton list (@list[0],).

How does the original triangular reduction know to make the first element of its output a singleton list?

If I write my own list-constructing routine it works like I would expect:

> sub foo { |$^a, $^b }
sub foo ($a, $b) { #`(Sub|93971926296448) ... }
> [[&foo]] 1..5
(1 2 3 4 5)
> [\[&foo]] 1..5
(1 (1 2) (1 2 3) (1 2 3 4) (1 2 3 4 5))

Answer 1

It's because the infix:<,> operator is list associative. Associativity is typically about deciding whether things group left or right (or not at all). Perl 6 also recognizes that some operators associate in a "flat" fashion, where we just want all of the values separated by the operator to be provided to the operator implementation at once.

If we declare an operator with default associativity and use it:

sub infix:<a>(*@a) {
    say @a.perl;
    return @a.elems;
};
say [\a] 1..5;

Then it will be called with just pairs of elements, giving the output:

[1, 2]
[2, 3]
[2, 4]
[2, 5]
(1 2 2 2 2)

However, change that to be list associative by adding the is assoc('list') trait:

sub infix:<a>(*@a) is assoc('list') {
    say @a.perl;
    return @a.elems;
};
say [\a] 1..5;

Then the output is instead:

[1]
[1, 2]
[1, 2, 3]
[1, 2, 3, 4]
[1, 2, 3, 4, 5]
(1 2 3 4 5)

Which is how infix:<,> gets its nice triangle reduction behavior.

Answer 2

I was about to publish when Jonathan posted his answer. I'd trust his worst answer to anything before my best to anything but what the hey, here's what I had, even if it's completely wrong.

---

Having gone away and returned a couple days later I still imagine my answer is somewhat helpful despite Jonathan's. Anyhoo, I've rewritten mine to best distill it to its simple essence.

---

It's not about the triangular aspect. That's just consistent with the underlying basic reduction.

Applying , to a single element yields a single element list

You wrote:

[\op] @list should evaluate to (@list[0], @list[0] op @list[1], ...).

Not necessarily. Per the doc for the reduce routine (with my added emphasis):

If @list contains just a single element, the operator is applied to that single element if possible; if not, it returns the element itself.

It's possible to use a , with a single element, yielding a single element list:

say .gist given 42   ; # 42
say .gist given 42 , ; # (42)
say .perl given 42 , ; # (42,)

And so:

say [,]  42;    # (42)
say [,]  42,99; # (42 99)

So an ordinary reduction with the comma operator always produces a list even when it's a reduction of a single element. And triangular reduction just follows suit:

say [\,] 42;    # ((42))
say [\,] 42,99; # ((42) (42 99))