Implementing monads in JavaScript

Question

Now that node.js supports ECMAScript Harmony generators we can write monadic code succinctly ala do blocks in Haskell:

function monad(unit, bind) {
    return function (f) {
        return function () {
            var g = f.apply(this, arguments);

            return typeOf(g) === "Generator" ? send() : unit(g);

            function send(value) {
                var result = g.next(value);
                if (result.done) return unit(result.value);
                else return bind(result.value, send);
            }
        };
    };
}

function typeOf(value) {
    return Object.prototype.toString.call(value).slice(8, -1);
}

In the code above monad is a function which can be used to create deterministic monads like:

var maybe = monad(function (a) {
    return {just: a};
}, function (m, f) {
    return m === null ? null : f(m.just);
});

You may now use maybe as follows:

var readZip = maybe(function * (a, b) {
    var a = yield readList(a);
    var b = yield readList(b);
    return _.zip(a, b);
});

The above function readZip takes two strings, converts them into lists and then zips them. If there's an error then it immediately returns null. It depends upon the following function:

function readList(string) {
    try {
        var value = JSON.parse(string);
        return value instanceof Array ? {just: value} : null;
    } catch (error) {
        return null;
    }
}

We test it to check whether it works as it's expected to:

console.log(readZip('[1,2,3,4]', '["a","b"]')); // [[1,"a"],[2,"b"],[3,"c"]]
console.log(readZip('hello', '["a","b"]'));     // null
console.log(readZip('[1,2,3,4]', 'world'));     // null

Similarly we can create any other deterministic monad. For example, my favorite, the cont monad:

var cont = monad(function (a) {
    return function (k) {
        return k(a);
    };
}, function (m, k) {
    return function (c) {
        return m(function (a) {
            return k(a)(c);
        });
    };
});

Now we can use cont to create functions in continuation passing style succinctly:

var fib = cont(function * (n) {
    switch (n) {
    case 0: return 0;
    case 1: return 1;
    default:
        var x = yield fib(n - 1);
        var y = yield fib(n - 2);
        return x + y;
    }
});

You can use the fib function as follows:

fib(10)(function (a) { console.log(a); }); // 55

Unfortunately monad only works for deterministic monads. It doesn't works for non-deterministic monads like the list monad because you can only resume a generator from a specific position once.

So my question is this: is there any other way to implement non-deterministic monads like the list monad succinctly in JavaScript?

Answer 1

So my question is this: is there any other way to implement non-deterministic monads like the list monad succinctly in JavaScript?

Yes, you can implement non-deterministic monads like the list monad succinctly in JavaScript using generators, à la immutagen. However, because generators in JavaScript can't be resumed from a specific position multiple times, you have to emulate this behavior by creating and replaying multiple generators. This solution has several disadvantages.

1. It's inefficient because multiple generators need to be created and replayed, leading to quadratic growth in time complexity.
2. It only works for pure monads and pure computations because multiple generators need to be created and replayed. Hence, side effects would be incorrectly executed multiple times.

What we need in order to create non-deterministic monads such as the list monad are immutable generators. An immutable generator can be resumed from a specific position multiple times. Unfortunately, JavaScript doesn't natively support immutable generators. However, we can emulate it by creating and replaying multiple mutable generators. So, let's look at how to create an immutable generator.

The first problem we need to solve is a way is replay a mutable generator to a specific point. We do this using a special class of functions called regenerators. A regenerator is any function which returns a mutable generator. The simplest example of such a function is function* () {}. Thus, every generator function is a regenerator, but not every regenerator is a generator function. You can create new regenerators by advancing an old regenerator using the following function.

// type Regenerator = Arguments -> MutableGenerator

// next :: (Regenerator, Arguments) -> Regenerator
const next = (regen, ...args) => data => {
    const gen = regen(...args);
    return gen.next(data), gen;
};

The next function can be used to advance a regenerator to a specific point. For example, consider the following code snippet.

const next = (regen, ...args) => data => {
    const gen = regen(...args);
    return gen.next(data), gen;
};

const regen1  = next(regen0, 1, 2, 3);
const regen2  = next(regen1, undefined); // first value of mutable generator ignored
const regen3  = next(regen2, 10);

const gen1 = regen3(20);
const gen2 = regen3(30);

const result1 = gen1.next(40).value; // 10 + 20 + 40
const result2 = gen2.next(50).value; // 10 + 30 + 50

console.log(result1, result2);

function* regen0(a, b, c) {
    const x = yield a;
    const y = yield b;
    const z = yield c;
    return x + y + z;
}

As you can see, we can either advance a regenerator using the next function or apply a regenerator to a value to obtain a mutable generator. Now that we have the ability to replay a mutable generator to a specific point, we can create immutable generators as follows.

// immutagen :: Regenerator -> Arguments -> ImmutableGenerator
const immutagen = regen => (...args) => function loop(regen) {
    return (gen, data) => {
        const {value, done} = gen.next(data);
        if (done) return {value, next: null};

        let replay = false;
        const recur = loop(next(regen, data));
        return {value, next: value => {
            if (replay) return recur(regen(data), value);
            replay = true; return recur(gen, value);
        }};
    };
}(next(regen, ...args))(regen(...args));

The immutagen function can be used to create immutable generator functions, which we can call to yield immutable generators. Following is an example on how to create and use immutable generators.

const next = (regen, ...args) => data => {
    const gen = regen(...args);
    return gen.next(data), gen;
};

const immutagen = regen => (...args) => function loop(regen) {
    return (gen, data) => {
        const {value, done} = gen.next(data);
        if (done) return {value, next: null};

        let replay = false;
        const recur = loop(next(regen, data));
        return {value, next: value => {
            if (replay) return recur(regen(data), value);
            replay = true; return recur(gen, value);
        }};
    };
}(next(regen, ...args))(regen(...args));

const foo = immutagen(function* (a, b, c) {
    const x = yield a;
    const y = yield b;
    const z = yield c;
    return x + y + z;
});

const bar = foo(1, 2, 3).next(10).next(20);

const result1 = bar.next(30).value; // 10 + 20 + 30
const result2 = bar.next(40).value; // 10 + 20 + 40

console.log(result1, result2);

Finally, now that we have immutable generators we can implement non-deterministic monads like the list monad more succinctly as follows:

const next = (regen, ...args) => data => {
    const gen = regen(...args);
    return gen.next(data), gen;
};

const immutagen = regen => (...args) => function loop(regen) {
    return (gen, data) => {
        const {value, done} = gen.next(data);
        if (done) return {value, next: null};

        let replay = false;
        const recur = loop(next(regen, data));
        return {value, next: value => {
            if (replay) return recur(regen(data), value);
            replay = true; return recur(gen, value);
        }};
    };
}(next(regen, ...args))(regen(...args));

const monad = bind => regen => (...args) => function loop({value, next}) {
    return next ? bind(value, val => loop(next(val))) : value;
}(immutagen(regen)(...args));

const flatMap = (array, callback) => array.flatMap(callback);

const list = monad(flatMap);

const foo = list(function* (xs, ys) {
    const x = yield xs;
    const y = yield ys;
    return [x * y];
});

console.log(foo([1, 2, 3], [4, 5, 6]));

Note that the monad function only needs bind. It doesn't need unit.

Answer 2

So my question is this: is there any other way to implement non-deterministic monads like the list monad succinctly in JavaScript?

I suggest this monad implementation, that I applied to various monads here:

var extend = function(a, b) {
  for (var i in b)
    a[i] = b[i];
  return a;
};

// Chain a new `this`
var fluent = function(f) {
  return function() {
    var clone = extend(Object.create(null), this);
    f.apply(clone, arguments);
    return clone;
  };
};

var toArray = function(x) {
  return Array.prototype.slice.call(x);
};

var List = {
  unit: fluent(function() {
    this.x = toArray(arguments);
  }),
  bind: function(f) {
    var fx = this.x.map(f.bind(this));
    var a = fx[0];
    for (var i=1; i<fx.length; i++)
      a.x = a.x.concat(fx[i].x);
    return a;
  },
  lift: function(f) {
    return function(x) {
      return List.unit(f(x));
    }
  },
  valueOf: function() {
    return this.x;
  }
};

var add1 = function(x) {
  return x + 1;
};

// Laws
var m = List.unit(3);
var f = List.lift(add1);

var laws = [
  m.bind(f)[0] == f(3)[0],
  m.bind(function(x){ return List.unit(x) })[0] == m[0],
  m.bind(function(x){ return f(x).bind(f) })[0] == m.bind(f).bind(f)[0]
];

console.log(laws); //=> [true, true, true]

// lift
var result = List.unit(1,2).bind(List.lift(add1)); //=> [2,3]

console.log(result.valueOf());

// do
var result = List.unit(1,2).bind(function(x) {
  return this.unit(3,4).bind(function(y) {
    return this.unit(x + y);
  });
});

console.log(result.valueOf()); //=> [4,5,5,6]

Obviously the "do" syntax leads to callback hell, but in LiveScript you can ease the pain:

result = do
  x <- List.unit 1 2 .bind
  y <- @unit 3 4 .bind
  @unit x + y

You could also name your bind method creatively:

result = do
  x <- List.unit 1 2 .\>=
  y <- @unit 3 4 .\>=
  @unit x + y

Answer 3

There seems to be a nifty way to implement a list monad like this:

function* unit(value) {
    yield value;
}
function* bind(list, transform) {
    for (var item of list) {
        yield* transform(item);
    }
}
var result = bind(['a', 'b', 'c'], function (element) {
    return bind([1, 2, 3], function* (element2) {
        yield element + element2;
    });
});
for (var item of result) {
    console.log(item);
}

based on https://curiosity-driven.org/monads-in-javascript#list

Answer 4

because you can only resume a generator from a specific position once.

Since all the solutions that purport to clone iterators actually give quadratic-ish complexity (technically O(|yield depth| * |num of iterators|)), perhaps the solution is to avoid iterators as much as possible and... as ugly as it is, instead write the relevant parts of the program in continuation-passing style. After all, a continuation may return more than once. And I thought the continuation monad is universal in that other monads can be implemented with it.

Perhaps one could then do some sort of syntactic transformation (perhaps even at runtime) to make life easier and not have giant nested function statements. Though, you did have a pretty call/cc-but-in-CPS in a previous answer of yours.

We could use a javascript parser written in javascript, such as https://esprima.org/, to look at the source code by inspecting the function's .toString(). Then transform it into CPS.

For example, perhaps we could say:

decoCPS(
function square(x) {
    return x**2;
});

decoCPS(
function hypotenuse(a,b) {
    var sqrt = Math.sqrt;
    let aSquared = a*a;
    return sqrt(aSquared+square(b));
});

Then this would be magically converted to CPS... things get more complicated if the user wants to use mutable state or non-confluent data structures (maybe pass in the state via some kind of continuation-and-state monad... prototypical inheritance is slow but a Proxy might help), but if we currently only care about functions, we could say "since we might wish to return a function which closes over a variable, whenever we would assign a variable... or whenever we call a function (even in the middle of an expression)... generate the continuation of that computation" in a recursive manner:

hypotenuse(a,b) {
    // original code
}

step 1: params transformed:

hypotenuse.cps = function hypotenuseCps(k, a,b) {
    var sqrt = Math.sqrt;
    let aSquared = a*a;
    return sqrt(aSquared+square(b));
}

step 2-9999: ??? Here I'm lost... I'm not sure the exact direct-style-to-CPS transform in excruciating full detail. I've seen some considerations here and here. It can get hairy with function calls in the middle of an expression, but the parser does give you the AST to play with.

Perhaps one would first turn return statements into either k(returned value, function restOfComputationHere{...}), then after the transform is complete, if a global is set to enable trampoline-style, convert back to a thunk or some sort of wrapper for the thunk like return new TrampolineCallMeNext(k, {args:[returned value], callback:function restOfComputationHere{...}}). This would give the user the choice of whether to always abuse the SetTimeout mechanism of ecmascript which may cause excessive slowdown.

Then I'm not sure if the general syntactic transform progresses backwards line-by-line and/or subexpr-by-subexpr... I'm sure you know more about that and can piece it together from the above links. I would think though that perhaps a parser-generator (e.g. antlr or friends) might have some built-in way to do the CPS transform, but couldn't find any such thing.

I am not skilled at CPS or monads, so someone please correct me if I'm wrong here. Then you could implement whatever monad you want using the continuation monad. The first link gives an example of implementing the list monad using continuations.

Perhaps I am underestimating how pervasive a direct-to-CPS transform of a large section of program would be, with things like for-loops and other constructs.

Answer 5

You cannot abstratc from the nested computational structure in general in JS without compromising the effect layer or losing the ability of monads to determine the next effect depending on a previous value.

But at least you can abstract from chain by applying monads like applicatives:

const arrChain = mx => fm =>
  mx.reduce((acc, x) => arrAppend(acc) (fm(x)), []);

const arrAppend = xs => ys =>
  (xs.push.apply(xs, ys), xs);

const chain2 = chain => tx => ty => fm =>
  chain(chain(tx) (x => fm(x)))
    (gm => chain(ty) (y => gm(y)));

const main = chain2(arrChain)
  ([1,2])
    ([3,4])
      (x => [y => [x, y]]); // nested constructor application

// prev-val-next-eff-dependency:

const main2 = chain2(arrChain)
  ([1,2])
    ([3,4])
        (x =>
          x === 1
            ? []
            : [y => [x, y]]);

console.log(main);
console.log(main2);

This is slightly less efficient than the original computation because each effect is performed once in addition to unwrap the next action.

---

Here is another approach mixing monadic and continuation passing style. However, it is no replacement for do-notation either:

const chainv = ({chain}) => {
  const go = (mx, ...ms) => fm =>
    ms.length === 0
      ? chain(mx) (fm)
      : chain(mx) (x => fm(x) (go(...ms)));

  return go;
};

const arrChain = xs => fm =>
  xs.flatMap(fm);

const main = chainv({chain: arrChain}) (
  [1,2],
  [3,4],
  [5,6])
    (x => k =>
      k(y => k =>
        k(z => [x, y, z])));

// [1, 3, 5, 1, 3, 6, 1, 4, 5, 1, 4, 6, 2, 3, 5, 2, 3, 6, 2, 4, 5, 2, 4, 6]

const main2 = chainv({chain: arrChain}) (
  [1,2],
  [3,4],
  [5,6])
    (x => k =>
      x === 1
        ? []
        : k(y => k =>
          k(z => [x, y, z])));

// [2, 3, 5, 2, 3, 6, 2, 4, 5, 2, 4, 6]

console.log("main:", main);
console.log("main2:", main2);