Jez Higgins

Freelance software generalist
software created
extended or repaired


Older posts are available in the archive or through tags.

Feed

Follow me on Twitter
My code on GitHub

Contact
About

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 🙂


Tagged javascript, rillet, and code


Jez Higgins

Freelance software generalist
software created
extended or repaired

Older posts are available in the archive or through tags.

Feed

Follow me on Twitter
My code on GitHub

Contact
About