在JavaScript中实现monad

Question

现在node.js支持ECMAScript Harmony生成器,我们可以do在Haskell中简洁地编写monadic代码:

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

在上面的代码中monad是一个函数,可用于创建确定性 monad,如:

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

您现在可以使用maybe如下:

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

上面的函数readZip需要两个字符串,将它们转换为列表然后将它们拉链.如果有错误,则立即返回null.这取决于以下功能:

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

我们测试它以检查它是否按预期工作:

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

同样,我们可以创建任何其他确定性monad.例如,我最喜欢的,contmonad:

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

现在我们可以用cont简洁的方式创建连续传递样式的函数:

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

您可以使用以下fib功能:

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

不幸的是monad只适用于确定性的monad.它不适用于像listmonad 这样的非确定性monad,因为你只能从特定位置恢复一次发生器.

所以我的问题是:有没有其他方法可以list在JavaScript中简洁地实现monad这样的非确定性monad？

Answer 1

所以我的问题是:有没有其他方法可以在JavaScript中简洁地实现像monad一样的非确定性monad？

我建议这个monad实现,我在这里申请了各种monad :

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]

显然,"do"语法会导致回调地狱,但在LiveScript中你可以减轻痛苦:

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

您还可以bind创造性地命名您的方法:

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

Answer 2

\n

所以我的问题是：有没有其他方法可以像listJavaScript 中的 monad 一样简洁地实现非确定性 monad？

\n

\n\n

是的，您可以使用生成器 \xc3\xa0 la immutagen在 JavaScript 中简洁地实现非确定性 monad，例如列表 monad 。但是，由于 JavaScript 中的生成器无法从特定位置多次恢复，因此您必须通过创建和重播多个生成器来模拟此行为。该解决方案有几个缺点。

\n\n

\n
1. 它效率低下，因为需要创建和重放多个生成器，导致时间复杂度呈二次方增长。
\n
2. 它仅适用于纯 monad 和纯计算，因为需要创建和重播多个生成器。因此，副作用会被多次错误执行。
\n

\n\n

为了创建非确定性 monad（例如列表 monad），我们需要的是不可变的生成器。不可变的生成器可以从特定位置多次恢复。不幸的是，JavaScript 本身并不支持不可变生成器。但是，我们可以通过创建和重放多个可变生成器来模拟它。那么，让我们看看如何创建一个不可变的生成器。

\n\n

我们需要解决的第一个问题是一种将可变生成器重播到特定点的方法。我们使用一类称为再生器的特殊函数来做到这一点。再生器是任何返回可变生成器的函数。这种函数最简单的例子是function* () {}。因此，每个生成器函数都是一个再生器，但并非每个再生器都是生成器函数。您可以使用以下函数推进旧的再生器来创建新的再生器。

\n\n

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

\n\n

该next函数可用于将再生器推进到特定点。例如，请考虑以下代码片段。

\n\n

\r\n

\r\n

const next = (regen, ...args) => data => {\r\n    const gen = regen(...args);\r\n    return gen.next(data), gen;\r\n};\r\n\r\nconst regen1  = next(regen0, 1, 2, 3);\r\nconst regen2  = next(regen1, undefined); // first value of mutable generator ignored\r\nconst regen3  = next(regen2, 10);\r\n\r\nconst gen1 = regen3(20);\r\nconst gen2 = regen3(30);\r\n\r\nconst result1 = gen1.next(40).value; // 10 + 20 + 40\r\nconst result2 = gen2.next(50).value; // 10 + 30 + 50\r\n\r\nconsole.log(result1, result2);\r\n\r\nfunction* regen0(a, b, c) {\r\n    const x = yield a;\r\n    const y = yield b;\r\n    const z = yield c;\r\n    return x + y + z;\r\n}

\r\n

\r\n

\r\n

\n\n

正如您所看到的，我们可以使用该函数推进再生器next，或者将再生器应用于一个值以获得可变生成器。现在我们能够将可变生成器重播到特定点，我们可以按如下方式创建不可变生成器。

\n\n

// immutagen :: Regenerator -> Arguments -> ImmutableGenerator\nconst immutagen = regen => (...args) => function loop(regen) {\n    return (gen, data) => {\n        const {value, done} = gen.next(data);\n        if (done) return {value, next: null};\n\n        let replay = false;\n        const recur = loop(next(regen, data));\n        return {value, next: value => {\n            if (replay) return recur(regen(data), value);\n            replay = true; return recur(gen, value);\n        }};\n    };\n}(next(regen, ...args))(regen(...args));\n

\n\n

该immutagen函数可用于创建不可变的生成器函数，我们可以调用该函数来生成不可变的生成器。以下是有关如何创建和使用不可变生成器的示例。

\n\n

\r\n

\r\n

const next = (regen, ...args) => data => {\r\n    const gen = regen(...args);\r\n    return gen.next(data), gen;\r\n};\r\n\r\nconst immutagen = regen => (...args) => function loop(regen) {\r\n    return (gen, data) => {\r\n        const {value, done} = gen.next(data);\r\n        if (done) return {value, next: null};\r\n\r\n        let replay = false;\r\n        const recur = loop(next(regen, data));\r\n        return {value, next: value => {\r\n            if (replay) return recur(regen(data), value);\r\n            replay = true; return recur(gen, value);\r\n        }};\r\n    };\r\n}(next(regen, ...args))(regen(...args));\r\n\r\nconst foo = immutagen(function* (a, b, c) {\r\n    const x = yield a;\r\n    const y = yield b;\r\n    const z = yield c;\r\n    return x + y + z;\r\n});\r\n\r\nconst bar = foo(1, 2, 3).next(10).next(20);\r\n\r\nconst result1 = bar.next(30).value; // 10 + 20 + 30\r\nconst result2 = bar.next(40).value; // 10 + 20 + 40\r\n\r\nconsole.log(result1, result2);

\r\n

\r\n

\r\n

\n\n

最后，现在我们有了不可变的生成器，我们可以更简洁地实现非确定性 monad，例如列表 monad，如下所示：

\n\n

\r\n

\r\n

const next = (regen, ...args) => data => {\r\n    const gen = regen(...args);\r\n    return gen.next(data), gen;\r\n};\r\n\r\nconst immutagen = regen => (...args) => function loop(regen) {\r\n    return (gen, data) => {\r\n        const {value, done} = gen.next(data);\r\n        if (done) return {value, next: null};\r\n\r\n        let replay = false;\r\n        const recur = loop(next(regen, data));\r\n        return {value, next: value => {\r\n            if (replay) return recur(regen(data), value);\r\n            replay = true; return recur(gen, value);\r\n        }};\r\n    };\r\n}(next(regen, ...args))(regen(...args));\r\n\r\nconst monad = bind => regen => (...args) => function loop({value, next}) {\r\n    return next ? bind(value, val => loop(next(val))) : value;\r\n}(immutagen(regen)(...args));\r\n\r\nconst flatMap = (array, callback) => array.flatMap(callback);\r\n\r\nconst list = monad(flatMap);\r\n\r\nconst foo = list(function* (xs, ys) {\r\n    const x = yield xs;\r\n    const y = yield ys;\r\n    return [x * y];\r\n});\r\n\r\nconsole.log(foo([1, 2, 3], [4, 5, 6]));

\r\n

\r\n

\r\n

\n\n

请注意，该monad函数仅需要bind. 它不需要unit。

\n