The Forest Road Reader, No 2.10 : Recreational Flattening

Thursday 22 November 2018 The Forest Road Reader, No 2.10 : Recreational Flattening

Spent a few minutes an evening or so back adding another couple of methods to Rillet, my JavaScript streams library. Sometimes it’s nice just to nurk around with code for no particular purpose.

The two new methods are flat and flatMap, and they have the same behaviour as the flatMap and flat Array methods currently going through the JavaScript standardisation process. The proposal’s currently at stage 3, which means they’re almost certain to go into the ES2019 standard.

Range.prototype.flat([depth]) flattens any iterables in the sequence, down to the depth given. The depth is optional and if omitted or is less that 1, it defaults to 1.
Range.prototype.flatMap(fn) applies fn to each item in the sequence, then flattens the result into a new sequence

Rillet already had flatten() which is, essentially, flat(∞), which is good because that’s not a method call you can actually make. flatMap(fn) is equivalent to map(fn).flat(1), but in this modern age clearer and, not uncoincidentally, a little more efficient in both time and space too.

One of the pleasing aspects of working on this code is that the implementations of these two methods are really straightforward. Here’s flat -

function* flat(iterable, depth) {
  for (const item of iterable)
    if (non_string_iterable(item) && depth > 1)
      yield* flat(item, depth-1);
    else
      yield item;
} // flat

Because we’re dealing with iterables, and so are lazily evaluating and only have to deal with the particular item at hand, we can lean on the magic of generators and yield and yield* to handle the book keeping. All we need to worry about is answering the does this one thing need flattening question.

Compare this with implementation for the proposed Array.prototype.flat. It has to exhaustively work through the array, examining every element within it, possibly flattening each one, examining elements within those, and so on and so on, until we’ve hit the desired depth limit. Here’s an (incomplete) example, lightly adapted from the core.js polyfill package.

function flat(depthArg = 1) {
  const O = toObject(this);
  const sourceLen = toLength(O.length);
  const A = arraySpeciesCreate(O, 0);
  A.length = flattenIntoArray(A, O, O, sourceLen, 0, depthArg);
  return A;
}

function flattenIntoArray (target, original, source, sourceLen, start, depth) {
  let targetIndex = start;
  let sourceIndex = 0;

  while (sourceIndex < sourceLen) {
    if (sourceIndex in source) {
      const element = source[sourceIndex];

      if (depth > 0 && isArray(element)) {
        targetIndex = flattenIntoArray(target, original, element, toLength(element.length), targetIndex, depth - 1) - 1;
      } else {
        target[targetIndex] = element;
      }
      targetIndex++;
    }
    sourceIndex++;
  }
  return targetIndex;
}

This isn’t in anyway to suggest that the core.js code is at all bad. It isn’t. It’s simply the case that flat for Arrays is going to be wordier that for streams. The heart of our two implementations is essentially the same - if this thing needs flattening then recurse, otherwise use it - which we can express as a single if/else. All the rest of the Array version, ie about 75% of it, is managing state that yield manages for us in the Rillet generator. Sequences are great, I’ve been saying so for years 🙂

javascript

rillet

code

Jez Higgins

Thursday 22 November 2018 The Forest Road Reader, No 2.10 : Recreational Flattening

Jez Higgins