# Day 23: Lazy fruits from the gather of Eden

Today’s gift is a construct not often seen in other languages. It’s an iterator builder! And it’s called `gather`.

But first, let’s try a bit of historical perspective. Many Perl people know their `map`, `grep` and `sort`, convenient functions to carry out simple list transformations, filterings and rankings without having to resort to `for` loops.

```my @squares = map { \$_ * \$_ }, @numbers;
my @primes  = grep { is-prime(\$_) }, @numbers;```

The `map` and `grep` constructs are especially powerful once we get comfortable with chaining them:

```my @children-of-single-moms =
map  {  .children },
grep { !.is-married },
grep {  .gender == FEMALE },
@citizens;```

(Note that `.children` may return one child, a list of several children or an empty list. `map` has a flattening influence on the lists thus produced, so the final result is a flat list of children.)

The chaining of `map` and `sort` gave rise to the famous Schwartzian transform, a Perl 5 caching idiom for when the thing being sorted on is computationally expensive:

```my @files-by-modification-date =
map  { .[0] },                # deconstruct
sort { \$^a[1] <=> \$^b[1] },
map  { [\$_, \$_ ~~ :M] },      # compute and construct
@files;```

It’s unfortunate that the functional paradigm puts the steps in reverse order of processing. The proposed pipe syntax, notably the `==>`, would solve that. But it’s not implemented in Rakudo yet, only described in S03.

Anyway, if you’ve read the post from day 20, you know that the Schwartzian transform is built into `sort` nowadays:

```my @files-by-modification-date =
sort { \$_ ~~ :M },
@files;```

So that’s, you know, coming along.

Now, what about this `gather` construct? Well, it’s a kind of generalization of `map` and `grep`.

```sub mymap(&transform, @list) {
gather for @list {
take transform(\$_);
}
};

sub mygrep(&condition, @list) {
gather for @list {
take \$_ if condition(\$_);
}
};```

(The real `map` can swallow several argument at a time, making it more powerful than the `&mymap` above.)

Just to be clear about what happens: `gather` signals that within the subsequent block, we’ll be building a list. Each `take` adds an element to the list. You could think of it as `push`ing to an anonymous array if you want:

```my @result = gather { take \$_ for 5..7 }; # this...

my @result;
push @result, \$_ for 5..7; # ...is the same as this```

Which brings us to the first property of `gather`: it’s the construct you can use for building lists when `map`, `grep` and `sort` aren’t sufficient. Of course, there’s no need to reinvent those constructions… but the fact that you can do that, or roll your own special variants, is kinda nice.

```sub incremental-concat(@list) {
my \$string-accumulator = "";
gather for @list {
# RAKUDO: The ~() is a workaround for [perl #62178]
take ~(\$string-accumulator ~= \$_);
}
};

say incremental-concat(<a b c>).perl; # ["a", "ab", "abc"]```

The above is nicer than using `map`, since we need to manage the `\$string-accumulator` between iterations.

(Implementing `&incremental-concat` by hand is silly in an implementation which implements the `[\~]` operator. Just a short announcement to people who want to keep track of the extent to which Perl 6 is channeling APL. Rakudo doesn’t yet, though.)

The second property of `gather` is that while the `take` calls (of course) have to occur within the scope of a `gather` block, they do not necessarily have to occur in the lexical scope, only the dynamic scope. For those unfamiliar with the distinction, I think an example explains it best:

```sub traverse-tree-inorder(Tree \$t) {
traverse-tree-inorder(\$t.left) if \$t.left;
take transform(\$t);
traverse-tree-inorder(\$t.right) if \$t.right;
}

my \$tree = ...;
my @all-nodes = gather traverse-tree-inorder(\$tree);```

See what’s happening here? We wrap the call to `&traverse-tree-inorder` in a `gather` statement. The statement itself doesn’t lexically contain any `take` calls, but the called subroutine does, and the `take` in there remembers that it’s in a gather context. That’s what makes the `gather` context dynamic rather than lexical.

Just to hammer in the point, `traverse-tree-inorder` does lexical recursion on a tree structure, and no matter how far down the call stack we find ourselves, the values passed to `take` find their way back into the same anonymous array, rooted in the `gather` around the original call. It’s as if the anonymous array were implicitly passed around for us automatically as invisible arguments. Another way to view it is that the `gather` mode works orthogonally to the call stack, essentially not caring about how many calls down it is.

Should we be unfortunate enough to do a `take` outside of any `gather` block, we’ll get a warning at runtime.

I’ve saved the best till last: the third property of `gather`: it’s lazy.

What does “lazy” mean here? Well, to take the above tree-traversing code as an example: when the assignment to `@all-nodes` has executed, the tree hasn’t yet been traversed. Only when you access the first element of the array, `@all-nodes[0]`, does the traversal start. And it stops right after it finds the leftmost leaf node. Access `@all-nodes[1]`, and the traversal will resume from where it left off, run just enough to find the second node in the traversal, and then stop.

In short, the code within the gather block starts and stops in such a way that it never does more work than you’ve asked it to do. That’s lazy.

It’s essentially a model of delayed execution. Perl 6 promises to run the code inside your gather block, but only if it turns out that you actually need the information. Operationally, you can think of it as a separate thread that starts and stops, always doing the smallest possible amount of work to keep the main thread satisfied. But under the hood in a given implementation, it’s likely implemented by continuations — or, failing that, by painful, complicated cheating.

Now here’s the thing: most any array in Perl 6 has the lazy behavior by default, and things like reading all lines from a file are lazy by default, and not only can `map` and `grep` be implemented using `gather`; it turns out that they actually are, too. So `map` and `grep` are also lazy.

Now, it’s nice to know that values aren’t unnecessarily generated when you’re doing calculations with arrays… but the really nice thing is that lazy arrays open up the door for stream-based programming and, by extension, infinite arrays.

Unfortunately, laziness hasn’t landed in Rakudo yet. We’re nearly there though, so I don’t feel too bad dangling these examples in front of you, even though they will currently cause Rakudo to spin the fans of your computer and nothing more:

```my @natural-numbers = 0 .. Inf;

my @even-numbers  = 0, 2 ... *;    # arithmetic seq
my @odd-numbers   = 1, 3 ... *;
my @powers-of-two = 1, 2, 4 ... *; # geometric seq

my @squares-of-odd-numbers = map { \$_ * \$_ }, @odd-numbers;

sub enumerate-positive-rationals() { # with duplicates, but still
take 1;
for 1..Inf -> \$total {
for 1..^\$total Z reverse(1..^\$total) -> \$numerator, \$denominator {
take \$numerator / \$denominator;
}
}
}

sub enumerate-all-rationals() {
map { \$_, -\$_ }, enumerate-positive-rationals();
}

sub fibonacci() {
gather {
take 0;
my (\$last, \$this) = 0, 1;
loop { # infinitely!
take \$this;
(\$last, \$this) = \$this, \$last + \$this;
}
}
}
say fibonacci[10]; # 55

# Merge two sorted (potentially infinite) arrays
sub merge(@a, @b) {
!@a && !@b ?? () !!
!@a        ?? @b !!
!@b ?? @a !!
(@a[0] < @b[0] ?? @a.shift !! @b.shift, merge(@a, @b))
}

sub hamming-sequence() # 2**a * 3**b * 5**c, where { all(a,b,c) >= 0 }
gather {
take 1;
take \$_ for
merge( (map { 2 * \$_ } hamming-sequence()),
merge( (map { 3 * \$_ }, hamming-sequence()),
(map { 5 * \$_ }, hamming-sequence()) ));
}
}```

(That last subroutine is a Perl 6 solution to the Hamming problem, described in section 6.4 of mjd++’s Higher Order Perl. A seriously cool book, by the way. It builds iterators from scratch; we just use `gather` for the same result.)

Today’s obfu award goes to David Brunton, who has written a Perl 6 tweet which draws a rule #30 cellular automaton, which also happens to look like a Christmas tree.

```\$ perl6 -e 'my %r=[^8]>>.fmt("%03b") Z (0,1,1,1,1,0,0,0);\
say <. X>[my@i=0 xx 9,1,0 xx 9];\
for ^9 {say <. X>[@i=map {%r{@i[(\$_-1)%19,\$_,(\$_+1)%19].join}},^19]};'
.........X.........
........XXX........
.......XX..X.......
......XX.XXXX......
.....XX..X...X.....
....XX.XXXX.XXX....
...XX..X....X..X...
..XX.XXXX..XXXXXX..
.XX..X...XXX.....X.
XX.XXXX.XX..X...XXX```