如何防止尾递归函数颠倒列表顺序？

Question

我正在尝试使用函数式的List类型和结构共享。由于Javascript没有尾递归模除法优化，因此我们不能像这样编写List组合器，因为它们不是堆栈安全的：

const list =
  [1, [2, [3, [4, [5, []]]]]];


const take = n => ([head, tail]) =>
  n === 0 ? []
    : head === undefined ? []
    : [head, take(n - 1) (tail)];


console.log(
  take(3) (list) // [1, [2, [3, []]]]
);

现在我尝试使用尾递归实现take函数，这样我就可以依靠TCO（在Ecmascript中仍然是一个未解决的Promise）或使用跳转器（为了保持简单，在示例中省略）：

const list =
  [1, [2, [3, [4, [5, []]]]]];


const safeTake = n => list => {
  const aux = (n, acc, [head, tail]) => n === 0 ? acc
    : head === undefined ? acc
    : aux(n - 1, [head, acc], tail);

  return aux(n, [], list);
};


console.log(
  safeTake(3) (list) // [3, [2, [1, []]]]
);

这个方法可行，但是新创建的列表是反向排序的。我该如何以纯函数式的方式解决这个问题呢？

- user6445533

---

你是在要求明确实现“尾调用取模cons”吗？ - Bergi

最简单的解决方案是从safeTake中返回reverse(aux(n, [], list))。 - Bergi

@Bergi，昨天我在另一个问题中询问了关于显式TRMC的问题。 - user6445533

@Bergi 我本来希望解释器能够聪明地识别我何时将一个数组用作List类型:D - user6445533

@Bergi PureScript？我更愿意探索将JavaScript弯曲到函数式风格的极限。 - user6445533

Answer 1

懒惰计算可以免费获得尾递归模除。因此，显而易见的解决方案是使用thunk。但我们不只是想要任何类型的thunk。我们需要一个在弱头规范形式中的表达式的thunk。在JavaScript中，我们可以使用延迟获取器来实现如下：

const cons = (head, tail) => ({ head, tail });

const list = cons(1, cons(2, cons(3, cons(4, cons(5, null)))));

const take = n => n === 0 ? xs => null : xs => xs && {
    head: xs.head,
    get tail() {
        delete this.tail;
        return this.tail = take(n - 1)(xs.tail);
    }
};

console.log(take(3)(list));

使用惰性获取器有很多优点：

1. 普通属性和惰性属性的使用方式相同。
2. 您可以使用它创建无限的数据结构。
3. 您不必担心堆栈溢出的问题。

希望这可以帮到您。

- Aadit M Shah

---

这确实非常有帮助！WHNF是否是Haskell社区中有时被称为保护递归的基本机制？我一直认为保护递归是一个复杂的编译器优化。但现在看来它实质上是惰性求值的副作用。 - user6445533

WHNF不是一种机制，惰性是机制。一个思路是：如果惰性是一个动词，那么WHNF就是一个名词。在WHNF中的表达式可能只被评估到最外层的构造器，构造器内的字段可能还没有被评估（由于惰性）。因此，惰性允许表达式处于WHNF状态。转而说，WHNF通过隐式跳板启用了受保护的递归。因此，通过传递性，惰性使您可以免费获得受保护的递归。 - Aadit M Shah

请注意，惰性并不是保护递归所必需的特性。例如，在 Scheme 这样的严格语言中，你也可以使用保护递归。在这种情况下，保护递归（即尾递归 modulo cons）确实是一种复杂的编译器优化。 - Aadit M Shah

Answer 2

防止列表反转的一种方法是使用继续传递风格。现在只需将其放在您选择的跳板上即可...

const None =
  Symbol ()

const identity = x =>
  x

const safeTake = (n, [ head = None, tail ], cont = identity) =>
  head === None || n === 0
    ? cont ([])
    : safeTake (n - 1, tail, answer => cont ([ head, answer ]))

const list =
  [ 1, [ 2, [ 3, [ 4, [ 5, [] ] ] ] ] ]

console.log (safeTake (3, list))
// [ 1, [ 2, [ 3, [] ] ] ] 

这是在蹦床上的样子。

const None =
  Symbol ()

const identity = x =>
  x

const call = (f, ...values) =>
  ({ tag: call, f, values })

const trampoline = acc =>
{
  while (acc && acc.tag === call)
    acc = acc.f (...acc.values)
  return acc
}

const safeTake = (n = 0, xs = []) =>
{
  const aux = (n, [ head = None, tail ], cont) =>
    head === None || n === 0
      ? call (cont, [])
      : call (aux, n - 1, tail, answer =>
          call (cont, [ head, answer ]))
  return trampoline (aux (n, xs, identity))
}

const list =
  [ 1, [ 2, [ 3, [ 4, [ 5, [] ] ] ] ] ]

console.log (safeTake (3, list))
// [ 1, [ 2, [ 3, [] ] ] ] 

- Mulan

---

当我使用loop/recur实现safeTake并将其应用于一个巨大的列表时，我会在answer => cont ([head，answer])处遇到堆栈溢出。你能重现这个问题吗？ - user6445533

@ftor，我在上面添加了一个蹦床演示。还记得chainRec的问题吗？我认为可以使用我们的堆栈安全续体单子或使用堆栈安全的unfold来重写它。 - Mulan

嗯，这似乎也会导致堆栈溢出：你的示例。这是我几个小时前的尝试。我不太明白，但似乎继续可能会形成真正的调用堆栈。 - user6445533

@ftor 在 aux 的所有返回路径中添加了 call - 这里是验证，使用一个不那么聪明的测试 它可以工作 :D - Mulan

谢谢，我自己修不好。我对 CPS 不是很擅长。 - user6445533