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

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 transformer

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

};

// variadic monadic lifting function

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

};

// asynchronous Task

const 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 function

const delay = (ms, x) =>

  Task(r => setTimeout(r, ms, x));

// test data

const 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 定律，它们的评估结果应该相同，但在实践中，一个可能比另一个更有效率。