在JavaScript中实现monad [英] Implementing monads in JavaScript

问题描述

现在 node.js 支持

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

在monad上面的代码中，有一个函数可用于创建确定性单子集，例如:

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

您现在可以按以下方式使用maybe:

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

上面的函数readZip接受两个字符串，将它们转换为列表，然后压缩它们.如果有错误，则立即返回null.它取决于以下功能:

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

类似地，我们可以创建任何其他确定性单子.例如，我最喜欢的cont monad:

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

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

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

您可以按以下方式使用fib函数:

You can use the fib function as follows:

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

不幸的是，monad仅适用于确定性Monad.它不适用于像list monad这样的不确定性monad，因为您只能从特定位置恢复一次生成器.

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.

所以我的问题是:还有其他方法可以在JavaScript中简洁地实现非确定性Monad，例如list monad吗?

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

推荐答案

所以我的问题是:还有其他方法可以在JavaScript中简洁地实现非确定性Monad，例如list monad吗?

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

是的，您可以使用生成器在JavaScript中简洁地实现非确定性monad，例如list monad，例如 immutagen .但是，由于无法多次从特定位置恢复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. 效率低下，因为需要创建并重播多个生成器，从而导致时间复杂度呈二次增长.
2. 它仅适用于纯monad和纯计算，因为需要创建并重播多个生成器.因此，副作用将被错误地多次执行.

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

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.

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

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

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

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

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

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

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

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

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

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

请注意，monad功能仅需要bind.不需要unit.

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

这篇关于在JavaScript中实现monad的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！