Strange loops in Haskell, but now in JavaScript! :D

The name of this function probably comes from Löb’s theorem, which is the mathematical analogue of the loeb function.

You may or may not want to read up on the original Haskell version and commentary by David Luposchainsky first.

For the adventurous, here’s a JSFiddle of this entire article (results will only appear in the developer console).

Remark about lazy evaluation

Since JavaScript uses strict/eager evaluation, lazy values must be indicated explicitly. We denote them here using the Lazy prefix:

-- Haskell
type Lazy a = () -> a

This makes the type signatures slightly more complicated than usual.

Löb

First, let’s look at the loeb function, specialized for arrays. The original lazy Haskell definition looked like this when written out fully:

-- Haskell
loeb :: [[a] -> a] -> [a]
loeb formulas = results
  where evaluate formula = formula results
        results = map evaluate formulas

In an eager language, this needs to be modified slightly:

-- Haskell
loeb :: [[Lazy a] -> a] -> [Lazy a]
loeb formulas = results
  where evaluate formula () = formula results
        results = map evaluate formulas

This has the slight downside of having to manually force out the results afterwards.

Translating into JavaScript is straightforward, but the code is uglier:

function loeb(formulas) {
    function evaluate(formula) { return function() {
        return formula(results);
    } }
    var results = formulas.map(evaluate);
    return results;
}

The typical use for this function is as a spreadsheet evaluator. Here’s an example of a simple 3-cell spreadsheet:

A1:       2
A2:       3
A3:  =A1+A2

console.log("spreadsheet result: ", loeb([
    function(cells) { return 2; },
    function(cells) { return 3; },
    function(cells) { return cells[0]() + cells[1](); }
]).map(function(x){ return x(); }))

The .map(function(x){ return x(); }) forces every cell to be evaluated. You should see [2, 3, 5] in the console.

Möb

The loeb function can be generalized by adding an explicit map parameter, allowing our choice of the mapping function.

The Haskell type signature looks quite scary, even though the implementation is virtually identical:

-- Haskell
moeb :: (((t -> a) -> Lazy a) -> s -> t) -> s -> t
moeb map formulas = results
  where evaluate formula () = formula results
        results = map evaluate formulas

But since we’re in JavaScript-land we don’t care about type signatures. We just copy-paste our implementation, but allow the map function to be chosen arbitrarily.

function moeb(map) { return function (formulas) {
    function evaluate(formula) { return function() {
        return formula(results);
    } }
    var results = map(evaluate)(formulas);
    return results;
} }

It’s easy to recover loeb from moeb. We just need to define a helper function (literally just a curried version of .map).

function map(func) { return function(array) {
    return array.map(func);
} }

Then, we have that:

var the_same_loeb = moeb(map);

See for yourself :p

We can also define the fixpoint combinator (a.k.a. Y combinator). But first we need another helper function, the identity function.

function id(x) {
    return x;
}

Then the fixpoint combinator is just:

var fix = moeb(id);

Here’s an example of using the fixpoint combinator to implement the factorial function. Not the sanest way of implementating factorials, I might add.

var factorial = fix(function(fac) { return function(x) {
    return x > 0 ? x * fac()(x - 1) : 1;
} })();
console.log("factorial of 3 is", factorial(3));