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

  • A+
Category:Languages

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

 


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.

Comment

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: