17

现在node.js支持ECMAScript Harmony 生成器do,我们可以在 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有一个函数可以用来创建确定性的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,仅适用于确定性单子。它不适用于像listmonad 这样的非确定性 monad,因为您只能从特定位置恢复生成器一次。

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

4

5 回答 5

7

所以我的问题是:有没有其他方法可以在 JavaScript 中简洁地实现非确定性 monad,比如 list 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
于 2013-12-22T14:30:54.273 回答
3

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

是的,您可以在 JavaScript 中使用生成器 à la immutagen简洁地实现非确定性 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);

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

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

于 2019-06-29T05:42:04.777 回答
1

在不损害效果层或失去单子根据先前值确定下一个效果的能力的情况下,您通常无法从 JS 中的嵌套计算结构中抽象出来。

但至少你可以chain通过应用像 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);

这比原始计算效率略低,因为除了展开下一个动作之外,每个效果都执行一次。


这是另一种混合单子和延续传递风格的方法。但是,它也不能替代 do-notation:

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

于 2020-07-09T19:04:07.110 回答
0

似乎有一种很好的方法来实现这样的列表单子:

function* unit(value) {
    yield value;
}
function* bind(list, transform) {
    for (var item of list) {
        yield* transform(item);
    }
}
var result = bind(['a', 'b', 'c'], function (element) {
    return bind([1, 2, 3], function* (element2) {
        yield element + element2;
    });
});
for (var item of result) {
    console.log(item);
}

基于https://curiosity-driven.org/monads-in-javascript#list

于 2015-08-10T09:35:08.743 回答
0

因为您只能从特定位置恢复生成器一次。

由于所有声称克隆迭代器的解决方案实际上都给出了二次复杂度(技术上 O(|yield depth| * |num of iterators|)),也许解决方案是尽可能避免迭代器并且......尽可能丑陋而是以延续传递风格编写程序的相关部分。毕竟,一个延续可能不止一次返回。而且我认为延续单子是通用的,因为其他单子可以用它来实现。

也许然后可以进行某种语法转换(甚至在运行时)以使生活更轻松,并且没有巨大的嵌套函数语句。不过,在您之前的回答中,您确实有一个漂亮的电话/cc-but-in-CPS。

我们可以使用用 javascript 编写的 javascript 解析器,例如https://esprima.org/,通过检查函数的.toString(). 然后将其转换为 CPS。

例如,也许我们可以说:

decoCPS(
function square(x) {
    return x**2;
});

decoCPS(
function hypotenuse(a,b) {
    var sqrt = Math.sqrt;
    let aSquared = a*a;
    return sqrt(aSquared+square(b));
});

然后这将神奇地转换为 CPS ...如果用户想要使用可变状态或非融合数据结构(可能通过某种连续和状态单子传递状态...原型继承),事情会变得更加复杂很慢,但代理可能会有所帮助),但如果我们目前只关心函数,我们可以说“因为我们可能希望返回一个关闭变量的函数,每当我们分配一个变量......或者每当我们调用函数(即使在表达式的中间)......以递归方式生成该计算的延续:

hypotenuse(a,b) {
    // original code
}

第 1 步:参数转换:

hypotenuse.cps = function hypotenuseCps(k, a,b) {
    var sqrt = Math.sqrt;
    let aSquared = a*a;
    return sqrt(aSquared+square(b));
}

步骤 2-9999:???在这里,我迷路了……我不确定确切的直接样式到 CPS 的转换是否具有令人痛苦的完整细节。我在这里这里看到了一些注意事项。表达式中间的函数调用可能会变得很麻烦,但解析器确实为您提供了 AST 来玩。

也许首先将 return 语句转换为k(returned value, function restOfComputationHere{...}),然后在转换完成后,如果将全局设置为启用蹦床样式,则将其转换回 thunk 或某种类型的 thunk 包装器,例如return new TrampolineCallMeNext(k, {args:[returned value], callback:function restOfComputationHere{...}}). 这将使用户可以选择是否总是滥用 ecmascript 的 SetTimeout 机制,这可能会导致过度减速。

那么我不确定一般句法转换是否逐行和/或逐个子表达式向后进展......我相信您对此了解更多,并且可以从上面的链接中将其拼凑起来。我认为虽然解析器生成器(例如 antlr 或朋友)可能有一些内置的方法来进行 CPS 转换,但找不到任何这样的东西。

我不擅长 CPS 或 monads,所以如果我在这里错了,请有人纠正我。然后你可以使用 continuation monad 来实现你想要的任何 monad。第一个链接给出了一个使用延续实现 list monad 的示例。

也许我低估了大部分程序的直接到 CPS 转换的普遍性,例如 for 循环和其他构造。

于 2021-03-01T06:54:47.430 回答