如何折叠来自非尾递归算法的数据结构？

Question

我有一个可变参数提升函数，它允许没有深度嵌套的函数组合的扁平 monadic 链：const varArgs = f => {  const go = args =>    Object.defineProperties(      arg => go(args.concat(arg)), {        "runVarArgs": {get: function() {return f(args)}, enumerable: true},        [TYPE]: {value: "VarArgs", enumerable: true}      });  return go([]);};const varLiftM = (chain, of) => f => { // TODO: replace recursion with a fold  const go = (ms, g, i) =>    i === ms.length      ? of(g)      : chain(ms[i]) (x => go(ms, g(x), i + 1));  return varArgs(ms => go(ms, f, 0));};它有效，但我想通过折叠从递归中抽象出来。正常的折叠似乎不起作用，至少不能与Task类型一起使用，const varLiftM = (chain, of) => f =>  varArgs(ms => of(arrFold(g => mx => chain(mx) (g)) (f) (ms))); // A因为行中的代数A会Task为每次迭代返回 a ，而不是部分应用的函数。如何用折叠替换非尾递归？这是当前递归实现的一个工作示例：const TYPE = Symbol.toStringTag;const struct = type => cons => {  const f = x => ({    ["run" + type]: x,    [TYPE]: type,  });  return cons(f);};// variadic argument transformerconst varArgs = f => {  const go = args =>    Object.defineProperties(      arg => go(args.concat(arg)), {        "runVarArgs": {get: function() {return f(args)}, enumerable: true},        [TYPE]: {value: "VarArgs", enumerable: true}      });  return go([]);};// variadic monadic lifting functionconst varLiftM = (chain, of) => f => { // TODO: replace recursion with a fold  const go = (ms, g, i) =>    i === ms.length      ? of(g)      : chain(ms[i]) (x => go(ms, g(x), i + 1));  return varArgs(ms => go(ms, f, 0));};// asynchronous Taskconst Task = struct("Task") (Task => k => Task((res, rej) => k(res, rej)));const tOf = x => Task((res, rej) => res(x));const tMap = f => tx =>  Task((res, rej) => tx.runTask(x => res(f(x)), rej));const tChain = mx => fm =>  Task((res, rej) => mx.runTask(x => fm(x).runTask(res, rej), rej));// mock functionconst delay = (ms, x) =>  Task(r => setTimeout(r, ms, x));// test dataconst tw = delay(100, 1),  tx = delay(200, 2),  ty = delay(300, 3),  tz = delay(400, 4);

Answer 1

那个of电话arrFold似乎有点不合适。

我不确定您arrFold是右折叠还是左折叠，但假设它是右折叠，您将需要像在递归实现中一样使用带有闭包的延续传递样式：

varArgs(ms => of(arrFold(g => mx => chain(mx) (g)) (f) (ms)))

变成

varArgs(ms => arrFold(go => mx => g => chain(mx) (x => go(g(x)))) (of) (ms) (f))

用左折叠，你可以写

varArgs(arrFold(mg => mx => chain(g => map(g) (mx)) (mg)) (of(f)))

但您需要注意，这构建了与正确折叠不同的调用树：

of(f)

chain(of(f))(g0 => map(m0)(g0))

chain(chain(of(f))(g0 => map(m0)(g0)))(g1 => map(m1)(g1))

chain(chain(chain(of(f))(g0 => map(m0)(g0)))(g1 => map(m1)(g1)))(g2 => map(m2)(g2))

vs（已经应用了延续）

of(f)

chain(m0)(x0 => of(f(x0)))

chain(m0)(x0 => chain(m1)(x1 => of(f(x0)(x1))))

chain(m0)(x0 => chain(m1)(x1 => chain(m2)(x2) => of(f(x0)(x1)(x2)))))

根据 monad 定律，它们的评估结果应该相同，但在实践中，一个可能比另一个更有效率。