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?

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 2

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 3

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);