*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:

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`

).

Then, we have that:

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.

Then the fixpoint combinator is just:

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

Show Disqus comments

comments powered by Disqus