Home | Contact

Poor Man's Time Machine

Here is a simpler version of the famous repmin puzzle from Richard Bird's arsenal of functional tricks: Given a non-empty array of numbers a, you have to find the smallest number m and replace every element of a with m in a single traversal.

Naive Non-Solution

It is straightforward to build a naive non-solution which calculates the minimum value of a in one pass and then mutates a in another pass:

function findMin(a) {
  let m = a[0]
  for (let i = 0; i < a.length; i++) {
    if (a[i] < m) {
      m = a[i]
    }
  }
  return m
}

function replaceMin(a, m) {
  for (let i = 0; i < a.length; i++) {
    a[i] = m
  }
}

const m = findMin(a)  // Pass #1
replaceMin(a, m)      // Pass #2

The question is: how do we perform these temporally dependent tasks in a single pass? That is, how do we go through a to replace all its elements with m but somehow also calculate m at the same time?

Basically, we need to traverse a to calculate m and simultaneously replace its elements with some value x which we can guarantee is going to be the minimum value.

But wait, won't that require sending a message to the present from the future?

So, is it necessary to invent a time machine to solve this puzzle? Or could we do with something more modest: say, a simple function and a tiny leap of faith?

A Function as an Unevaluated Value

To see how a simple function can help us, please note that the seemingly temporal dependency arises only because replaceMin(a, findMin(a)) forces the traversal in findMin before the replacement in replaceMin.

If we could just find a way to represent the minimum value not as a Number in JavaScript but as a function instead, the temporal dependency would vanish because a function doesn't need to be evaluated immediately. We can just replace every element of a with a function which would evaluate to the minimum value later. This function is then a proxy for m which delays the need to actually calculate m when we enter replaceMin.

Let's do this with a function findAndReplaceMin which calculates m but also replaces the elements of a by some as-of-yet unrelated function xf in a single pass:

function findAndReplaceMin(a, xf) {
  let m = a[0]
  for (let i = 0; i < a.length; i++) {
    if (a[i] < m) {
      m = a[i]
    }
    a[i] = xf
  }
  return m
}

Note that findAndReplaceMin receives xf as an argument and replaces every element of a with it. We still need to choose xf so that every occurrence of xf eventually yields the minimum value, even though that minimum has not yet been computed.

This seems like a problem. We're still stuck in a situation where computing m requires calling findAndReplaceMin with xf, but xf must already know how to produce m before findAndReplaceMin has computed it.

Make Evidence for Faith

This seems like a real problem until we realise that we can bootstrap the evidence for our faith by saying this:

let m = findAndReplaceMin(a, () => m)

This seems paradoxical: how can m be used in its own definition?

The answer is subtle: we are NOT using m to calculate m but only denoting m in a function which calculates m independently of the denotation.

More precisely, the closure () => m captures the variable m, which has not been initialised yet, without forcing its evaluation, which would happen only when we say xf(). And if you look carefully, we take care not to do that anywhere inside findAndReplaceMin (more on this in a bit).

When the line let m = findAndReplaceMin(a, () => m) is executed, it does two separate tasks in one single pass:

  1. Calculate the minimum value by traversing a and bind it to m
  2. Replace every element of a with the function () => m (without evaluating the function)

Contrast the line above with the obviously invalid declaration let m = m, which immediately attempts to read the value of m before it has been initialised.

By comparison, let m = findAndReplaceMin(a, () => m) never reads m during the construction of the closure. The expression () => m merely records how to obtain m in the future. The actual lookup is postponed until the function is called.

Note that after findAndReplaceMin has run, a is populated by functions and not Numbers. So, when any element of a is needed, we get it by calling a[i](), which reads the value bound to m. Note that this doesn't need to run findAndReplaceMin again because m is already bound to the minimum value from Step 1.

In functional parlance, writing this self-referential declaration is close to what is called tying the knot. It refers to the circular reference to m, which we fill from findAndReplaceMin in the future, but which we can still use inside findAndReplaceMin in the present if we take care not to inspect or evaluate it.

The key to this illusion of time travel is the assignment a[i] = xf without inspecting xf. We cannot afford to poke xf (say by doing xf()) inside findAndReplaceMin, because that would try to read m while we are still in the middle of computing it. JavaScript doesn't play along: it throws a ReferenceError on the spot, complaining that m cannot be accessed before initialisation.

I should reiterate that no law of physics is being broken here and no information is actually travelling backwards in time. We instinctively think of computation as a sequence of steps: first compute the minimum, then replace the elements. But tying the knot invites us to think equationally instead. Rather than saying let me calculate m first, we say here is how I'd like m to be defined given findAndReplaceMin, with the added benefit that the definition itself can be self-referential if we build it carefully.

We've almost solved this puzzle, but you might now complain: we were asked to create an array of Numbers but ended up creating an array of functions instead.

And the answer is that with standard primitives, we can't solve this perfectly in JavaScript without leaving behind an array of functions. (We could maybe pull off a solution using some advanced object metaprogramming, but that's probably a topic for another blog post!)

The Real Lazy Evaluation

To see how we can do exactly what we set out to, we look at a language where delayed evaluation is built in: Haskell.

Let's see what findAndReplaceMin would look like in Haskell:

findAndReplaceMin :: [Int] -> Int -> (Int, [Int])
findAndReplaceMin [y]     x  = (y, [x])
findAndReplaceMin (h : t) x  = (min g h, x : t')
  where (g, t') = findAndReplaceMin t x

let (m, b) = findAndReplaceMin a m

It almost mirrors the JavaScript logic, but recursively and immutably.

After findAndReplaceMin has run, the list b contains Ints in Haskell. But the same is not possible in JavaScript. Why?

The main reason is that in Haskell, we do not need to rely on closures to delay evaluation because values are lazy by default.

What that means in practice is that Haskell does not evaluate expressions just because they are passed as arguments or stored inside data structures. Instead, expressions are represented as unevaluated values (called thunks) and evaluated only when their values are demanded in some calculation. This evaluation strategy is known as call-by-need evaluation. An expression like findAndReplaceMin a m can be written without worrying about m being evaluated before findAndReplaceMin has finished. So, we don't need to resort to tricks like () => m just to delay evaluation of m. The expression bound to m remains unevaluated until some operation (mostly pattern-matching, or some function which needs m, like + or show) actually demands its value.

Compare this to JavaScript, where if we write findAndReplaceMin(a, m), both a and m would be evaluated before being passed to the function, which is why we need to wrap m inside () => ... to prevent JavaScript from poking. This style of evaluation is called call-by-value evaluation and is common in languages like C, Python, and JavaScript.

Also, tying the knot is relatively easier in Haskell. In Haskell, we can just write m on both sides of let (m, b) = findAndReplaceMin a m. A similar attempt in JavaScript is bound to fail, which is also why we took care to hide m inside () => m. But Haskell can construct cyclic graphs of thunks. The self-reference in let (m, b) = findAndReplaceMin a m does not require the runtime to know the value of m immediately. Instead, it creates a network of dependencies in which m and b can mutually refer to each other. Laziness ensures that these references are only followed when their values are actually needed.

Don't Peek Too Soon!

So it turns out we didn't need a time machine after all: just a function, a carefully deferred lookup, and the discipline not to peek too soon. But more importantly, in both languages, the trick explicitly relies on the same leap of faith: while lazy evaluation (Haskell) and the wrapper lambda (JavaScript) prevent automatic evaluation by the runtime, we ourselves cannot afford to peek into them (by pattern-matching on m in Haskell or calling xf in JavaScript) before findAndReplaceMin finishes execution.

If we get too impatient and lose faith, the knot comes undone in both languages. JavaScript refuses outright with a ReferenceError, while Haskell chases its own tail into an infinite abyss of doubt till time ends, unless GHC notices the loop first and gives up with a terse <<loop>>!