如何防止尾部递归函数反转列表的顺序? [英] How can I prevent a tail recursive function from reversing the order of a List?

问题描述

我正在尝试使用功能性List类型和结构共享.由于Javascript没有尾部递归模量优化，我们不能只是像这样写List组合器，因为它们不是堆栈安全的:

I am experimenting with the functional List type and structural sharing. Since Javascript doesn't have a Tail Recursive Modulo Cons optimization, we can't just write List combinators like this, because they are not stack safe:

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)或使用蹦床(在示例中为使事情简单而省略):

Now I tried to implement take tail recursively, so that I can either rely on TCO (still an unsettled Promise in Ecmascript) or use a trampoline (omitted in the example to keep things simple):

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

这有效，但是新创建的列表的顺序相反.我该如何以纯粹的功能方式解决此问题?

This works but the new created list is in reverse order. How can I solve this issue in a purely functional manner?

推荐答案

懒惰为您免费提供尾部递归模态缺点.因此，显而易见的解决方案是使用thunk.但是，我们不只是想要任何类型的重击.我们希望对弱头范式的表达式进行修改.在JavaScript中，我们可以使用惰性获取器如下:

Laziness gives you tail recursion modulo cons for free. Hence, the obvious solution is to use thunks. However, we don't just want any kind of thunk. We want a thunk for an expression in weak head normal form. In JavaScript, we can implement this using lazy getters as follows:

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

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

There are lots of advantages to using lazy getters:

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

希望有帮助.

这篇关于如何防止尾部递归函数反转列表的顺序?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！