在JavaScript中实现monad

Question

现在，node.js支持ECMAScript
Harmony生成器，
我们可以do在Haskell中简洁地编写ala代码单子代码了：

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有一个函数可用于创建 确定性 单子，例如：

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

同样，我们可以创建任何其他确定性单子。例如，我最喜欢的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仅适用于确定性单子。它不适用于像listmonad 这样的不确定的monad，因为您只能从特定位置恢复一次生成器。

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

Answer 1

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

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

1. 它的效率很低，因为需要创建并重播多个生成器，从而导致时间复杂度呈二次增长。
2. 它仅适用于纯monad和纯计算，因为需要创建并重播多个生成器。因此，副作用将被错误地多次执行。

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

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

// type Regenerator = Arguments -> MutableGenerator

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

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

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;

}

如您所见，我们可以使用该next函数推进再生器，或者将再生器应用于值以获得可变的生成器。现在，我们可以将可变的生成器重播到特定的位置，我们可以如下创建不可变的生成器。

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

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

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

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

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

请注意，该monad功能仅需要bind。不需要了unit。