How to avoid intermediate results when performing array iterations?

Question

When working with arrays, intermediate representations are needed regularly - particularly in connection with functional programming, in which data is often treated as immutable:

const square = x => x * x;
const odd = x => (x & 1) === 1;
let xs = [1,2,3,4,5,6,7,8,9];

// unnecessary intermediate array:
xs.map(square).filter(odd); // [1,4,9,16,25,36,49,64,81] => [1,9,25,49,81]

// even worse:
xs.map(square).filter(odd).slice(0, 2); // [1,9]

How can I avoid this behavior in Javascript/Ecmascript 2015 to obtain more efficient iterative algorithms?

Answer 1

Transducers are one possible way to avoid intermediate results within iterative algorithms. In order to understand them better you have to realize, that transducers by themselves are rather pointless:

// map transducer
let map = tf => rf => acc => x => rf(acc)(tf(x));

Why should we pass a reducing function to map for each invocation when that required function is always the same, concat namely?

The answer to this question is located in the official transducer definition:

Transducers are composable algorithmic transformations.

Transducer develop their expressive power only in conjunction with function composition:

const comp = f => g => x => f(g(x));
let xf = comp(filter(gt3))(map(inc));

foldL(xf(append))([])(xs);

comp is passed an arbitrary number of transducers (filter and map) and a single reduction function (append) as its final argument. From that comp builds a transformation sequence that requires no intermediate arrays. Each array element passes through the entire sequence before the next element is in line.

At this point, the definition of the map transducer is understandable: Composability requires matching function signatures.

Note that the order of evaluation of the transducer stack goes from left to right and is thus opposed to the normal order of function composition.

An important property of transducers is their ability to exit iterative processes early. In the chosen implementation, this behavior is achieved by implementing both transducers and foldL in continuation passing style. An alternative would be lazy evaluation. Here is the CPS implementation:

const foldL = rf => acc => xs => {
  return xs.length
   ? rf(acc)(xs[0])(acc_ => foldL(rf)(acc_)(xs.slice(1)))
   : acc;
};

// transducers
const map = tf => rf => acc => x => cont => rf(acc)(tf(x))(cont);
const filter = pred => rf => acc => x => cont => pred(x) ? rf(acc)(x)(cont) : cont(acc);
const takeN = n => rf => acc => x => cont =>
 acc.length < n - 1 ? rf(acc)(x)(cont) : rf(acc)(x)(id);

// reducer
const append = xs => ys => xs.concat(ys);

// transformers
const inc = x => ++x;
const gt3 = x => x > 3;

const comp = f => g => x => f(g(x));
const liftC2 = f => x => y => cont => cont(f(x)(y));
const id = x => x;

let xs = [1,3,5,7,9,11];

let xf = comp(filter(gt3))(map(inc));
foldL(xf(liftC2(append)))([])(xs); // [6,8,10,12]

xf = comp(comp(filter(gt3))(map(inc)))(takeN(2));
foldL(xf(liftC2(append)))([])(xs); // [6,8]

Please note that this implementation is more of a proof of concept and no full-blown solution. The obvious benefits of transducers are:

• no intermediate representations
• purely functional and concise solution
• genericity (work with any aggregate/collection, not just arrays)
• extraordinary code reusability (reducers/transformers are common functions with their usual signatures)

Theoretically, CPS is as fast as imperative loops, at least in Ecmascript 2015, since all tail calls have the same return point and can thereby share the same stack frame (TCO).

It is considered controversial whether this approach is idiomatic enough for a Javascript solution. I prefer this functional style. However, the most common transducer libraries are implemented in object style and should look more familiar to OO developers.