如何防止尾递归函数颠倒列表的顺序?
How can I prevent a tail recursive function from reversing the order of a List?
我正在试验功能 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 中仍然是未解决的 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, []]]]
);
这可行,但新创建的列表顺序相反。我怎样才能以纯功能的方式解决这个问题?
防止列表反转的一种方法是使用连续传递样式。现在只需将它放在您选择的蹦床上...
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, [] ] ] ]
Laziness 给你免费的尾递归模缺点。因此,显而易见的解决方案是使用 thunk。然而,我们不只是想要任何类型的thunk。我们想要 weak head normal form. In JavaScript, we can implement this using lazy getters 中的表达式的 thunk,如下所示:
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 有很多优点:
- 普通属性和惰性属性的使用方法相同。
- 您可以使用它来创建无限的数据结构。
- 您不必担心炸毁堆栈。
希望对您有所帮助。
我正在试验功能 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 中仍然是未解决的 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, []]]]
);
这可行,但新创建的列表顺序相反。我怎样才能以纯功能的方式解决这个问题?
防止列表反转的一种方法是使用连续传递样式。现在只需将它放在您选择的蹦床上...
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, [] ] ] ]
Laziness 给你免费的尾递归模缺点。因此,显而易见的解决方案是使用 thunk。然而,我们不只是想要任何类型的thunk。我们想要 weak head normal form. In JavaScript, we can implement this using lazy getters 中的表达式的 thunk,如下所示:
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 有很多优点:
- 普通属性和惰性属性的使用方法相同。
- 您可以使用它来创建无限的数据结构。
- 您不必担心炸毁堆栈。
希望对您有所帮助。