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

Question

我正在试验功能性 List 类型和结构共享。由于 Javascript 没有 Tail Recursive Modulo Cons优化，我们不能像这样编写 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 tail，这样我就可以依赖 TCO(在 Ecmascript 中仍然是 Unresolved 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, []]]]
);

这可行，但新创建的列表顺序相反。我怎样才能以纯函数的方式解决这个问题？

Answer 1

Laziness 为您免费提供了尾递归模 cons。因此，显而易见的解决方案是使用 thunk。然而，我们不只是想要任何类型的thunk。我们想要 weak head normal form 中的表达式的 thunk .在 JavaScript 中，我们可以使用 lazy getters 来实现它如下:

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

使用惰性 getter 有很多优点:

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

希望对您有所帮助。