如何将非尾递归算法的数据结构进行折叠？

Question

如何将非尾递归算法的数据结构进行折叠？

javascriptrecursionfunctional-programmingfoldrecursion-schemes

3

我有一个可变参数的lifting函数，允许扁平的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 而非部分应用函数。

我该如何使用 fold 替换尾递归？

下面是当前递归实现的工作示例：

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

// specialization through partial application

const varAsyncSum =
  varLiftM(tChain, tOf) (w => x => y => z => w + x + y + z);

// MAIN

varAsyncSum(tw) (tx) (ty) (tz)
  .runVarArgs
  .runTask(console.log, console.error);

console.log("1 sec later...");

[编辑] 根据评论中的要求，我实现了折叠功能：

const arrFold = alg => zero => xs => {
  let acc = zero;

  for (let i = 0; i < xs.length; i++)
    acc = alg(acc) (xs[i], i);

  return acc;
};

- user5536315

@cristy 这不是压缩代码，这是“函数式编程” :) - Jonas Wilms

2

给参数取ms、g、x、f、fm、of、tx、res和rej这样的名称，然后再同时使用它们（几乎是一起使用）对我来说看起来像是不必要的缩减，除非你知道它是关于什么的，否则会使代码变得更难以阅读。 - XCS

3

@Cristy，如果不是全部，那么大部分都是函数式编程中惯用语。类似于如果一个变量是计数器或索引，您会将其命名为i一样。f表示函数，g也是函数（在字母表中位于f之后，类似于在声明i之后使用j作为计数器），fm表示返回单子的函数，ms表示多个单子，因此为数组，of表示将类型提升为单子的函数。x是输入变量的通用名称。res和rej表示结果（成功）和拒绝（失败）。tx、ty和tz表示任务1、任务2和任务3。 - VLAZ

短名称只是反映了代码的一般性。例如，您可以在任何单子上使用varLiftM。要完成@VLAZ的名称传奇：“mx”代表单子值，“ms”代表单子值，“fm”代表单子操作（返回单子的函数）。 “tx”表示一个被封装在类型中的值，没有说明任何约束条件（即它是否单子、适用、functorial、遍历、foldable等）。 - user5536315

@Bergi 我一开始使用了 Object.assign，但是这会在复制过程中严格调用 getter... 感谢您提供的属性描述符提示，问题已经解决。 - user5536315

显示剩余4条评论

2个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Bergi · Answer 1

那个关于“arrFold”的“of”调用似乎有点不合适。

我不确定您的“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))

With a left fold, you could write

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

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

- Aadit M Shah · Answer 2

你不需要完整的Monad来处理这个特定的用例。Applicative Functor就足够了：

// type Cont r a = (a -> r) -> r

// type Async a = Cont (IO ()) a

// pure :: a -> Async a
const pure = a => k => k(a);

// ap :: Async (a -> b) -> Async a -> Async b
const ap = asyncF => asyncA => k => asyncF(f => asyncA(a => k(f(a))));

// delay :: (Number, a) -> Async a
const delay = (ms, a) => k => setTimeout(k, ms, a);

// async1, async2, async3, async4 :: Async Number
const async1 = delay(100, 1);
const async2 = delay(200, 2);
const async3 = delay(300, 3);
const async4 = delay(400, 4);

// sum :: Number -> Number -> Number -> Number -> Number
const sum = a => b => c => d => a + b + c + d;

// uncurry :: (a -> b -> c) -> (a, b) -> c
const uncurry = f => (a, b) => f(a)(b);

// result :: Async Number
const result = [async1, async2, async3, async4].reduce(uncurry(ap), pure(sum));

// main :: IO ()
result(console.log);
console.log("1 second later...");

如果您想的话，您可以按照以下方式定义一个应用程序上下文函数（即apply）。

const apply = (asyncF, ...asyncArgs) => asyncArgs.reduce(uncurry(ap), asyncF);

const result = apply(pure(sum), async1, async2, async3, async4);

如果你对这个函数进行柯里化，那么你就可以创建一个 lift 函数：

const apply = asyncF => (...asyncArgs) => asyncArgs.reduce(uncurry(ap), asyncF);

const lift = f => apply(pure(f));

const asyncSum = lift(sum);

const result = asyncSum(async1, async2, async3, async4);

注意，reduce 相当于 arrFold。因此，lift 相当于 varLiftM。