The blog of dlaa.me

I stumbled across a programming challenge while looking for info on UglifyJS. It's called A little JavaScript problem, though I you can do it in any language. I will summarize the problem here, but please visit that page for the details:

The problem: define functions range, map, reverse and foreach, obeying the restrictions below, such that the following program works properly. It prints the squares of numbers from 1 to 10, in reverse order.

var numbers = range(1, 10);
numbers = map(numbers, function (n) { return n * n });
numbers = reverse(numbers);
foreach(numbers, console.log);

This wouldn't be too hard, except the restrictions say you are not allowed to use Array or Object (i.e., no storing state in a lookup). So, yeah, it's a good challenge!

If you're interested, please try to do it before reading further - spoilers follow...

The first solution

My first thought was to use something like IEnumerable in .NET where range would generate the sequence of numbers and the other functions would consume that sequence and output a modified sequence in turn until foreach wrote each item to the console. I thought of this as a "generator" model (yes, I know JavaScript has generator functions, that's next...) and it's easy to define range as returning a function that returns one number each time it's called and a falsy value to signal the end.

function range (a, b) {
  return () => (a <= b) ? a++ : null;
}

That done, it's pretty straightforward to define foreach as a function that takes one of these "generators" and keeps calling it and processing results until they run out. (Yes, this has a bug if the range includes the value 0, but we could use a unique sentinel value to fix that.)

function foreach (g, func) {
  while (v = g()) {
    func(v);
  }
}

It's also easy to define map as taking one of these generator functions and returning another that returns the result of calling the provided function for each of the generated values in turn.

function map (g, func) {
  return () => func(g());
}

But reverse is more challenging! The only way to return the last item first is to traverse the entire list, but once that's done it can't be done again, so all the preceding elements need to be saved somewhere to be able to return them in backwards order. But recall that the code is not allowed to use arrays or objects, so typical data structures like Stack are not available. The approach I came up with was to create breadcrumbs out of closures. There might be a more elegant way to express this, but I did so with a local variable and helper methods push and pop. For each element in the list, a new closure is created that captures the previous closure and the value of the element. Returning values in reverse is then just a matter of looking into the current closure, replacing it with the previous closure, and returning the current closure's value. It's probably not immediately obvious what's going on with this code and it took a little while to come up with the right approach even after I had the design in my head.

function reverse (g) {
  let pop = () => null;
  const push = (v, pre) =>
    pop = () => (pop = pre) && v;
  while (v = g()) {
    push(v, pop);
  }
  return () => pop();
}

"She may not look like much, but she's got it where it counts, kid." But we can do better! I hadn't previously worked with JavaScript generators, and this seemed like a great opportunity to sharpen the saw...

The second solution

You're almost always better off using the right tool for the job; in this case generators/iterators fit nicely. As before, range is easy to get started with - just return the numbers in order and stop after the last one. In this case, the generator automatically indicates completion, so there is no confusion or ambiguity around returning a falsy value to signal the end.

function* range (a, b) {
  while (a <= b) {
    yield a++;
  }
}

The implementation of foreach is almost identical to before.

function foreach (g, func) {
  for (let v of g) {
    func(v);
  }
}

The code for map is very slightly longer than before, but it's completely obvious what it's doing and it's easy to write. (It looks a lot like foreach which is a win from an consistency point of view.)

function* map (g, func) {
  for (let v of g) {
    yield func(v);
  }
}

That brings us to reverse and that is where the real payoff happens! The generator-based version of this code also builds up state in the call chain (known as a "call stack" for a reason), but the way it does so is clear and closely relates to how one would describe this function in words: "until you're done, get the first value, reverse the rest of the list, and return the value (i.e., after the other values)".

function* reverse (g) {
  const { done, value } = g.next();
  if (!done) {
    yield* reverse(g);
    yield value;
  }
}

I'm much happier with this second solution because the intent is so much clearer. Also, it took me less time to write! :)

And there you have it: two solutions to the same problem. The first: functional but hard to follow; the second: clear and easy to understand (also more versatile). Sometimes, the right algorithm or approach can make a world of difference when it comes to programming.