https://stackoverflow.com/questions/20729050
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianSo my question is this: is there any other way to implement non-deterministic monads like the
listmonad 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.
- It's inefficient because multiple generators need to be created and replayed, leading to quadratic growth in time complexity.
- 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.
