是否可以使用延续使 foldRight 尾递归? [英] Is it possible to use continuations to make foldRight tail recursive?
问题描述
以下博客文章展示了如何在 F# foldBack
可以使用 continuation 传递样式进行尾递归.
The following blog article shows how in F# foldBack
can be made tail recursive using continuation passing style.
在 Scala 中,这意味着:
In Scala this would mean that:
def foldBack[T,U](l: List[T], acc: U)(f: (T, U) => U): U = {
l match {
case x :: xs => f(x, foldBack(xs, acc)(f))
case Nil => acc
}
}
可以通过这样做使尾递归:
can be made tail recursive by doing this:
def foldCont[T,U](list: List[T], acc: U)(f: (T, U) => U): U = {
@annotation.tailrec
def loop(l: List[T], k: (U) => U): U = {
l match {
case x :: xs => loop(xs, (racc => k(f(x, racc))))
case Nil => k(acc)
}
}
loop(list, u => u)
}
不幸的是,我仍然遇到长列表的堆栈溢出.循环是尾递归和优化的,但我猜堆栈累积只是移到了继续调用中.
Unfortunately, I still get a stack overflow for long lists. loop is tail recursive and optimized but I guess the stack accumulation is just moved into the continuation calls.
为什么这不是 F# 的问题?有什么办法可以用 Scala 解决这个问题吗?
Why is this not a problem with F#? And is there any way to work around this with Scala?
编辑:这里有一些显示堆栈深度的代码:
Edit: here some code that shows depth of stack:
def showDepth(s: Any) {
println(s.toString + ": " + (new Exception).getStackTrace.size)
}
def foldCont[T,U](list: List[T], acc: U)(f: (T, U) => U): U = {
@annotation.tailrec
def loop(l: List[T], k: (U) => U): U = {
showDepth("loop")
l match {
case x :: xs => loop(xs, (racc => { showDepth("k"); k(f(x, racc)) }))
case Nil => k(acc)
}
}
loop(list, u => u)
}
foldCont(List.fill(10)(1), 0)(_ + _)
打印:
loop: 50
loop: 50
loop: 50
loop: 50
loop: 50
loop: 50
loop: 50
loop: 50
loop: 50
loop: 50
loop: 50
k: 51
k: 52
k: 53
k: 54
k: 55
k: 56
k: 57
k: 58
k: 59
k: 60
res2: Int = 10
推荐答案
问题在于延续函数 (racc => k(f(x, racc)))
本身.它应该为整个业务进行优化,使其正常工作,但事实并非如此.
The problem is the continuation function (racc => k(f(x, racc)))
itself. It should be tailcall optimized for this whole business to work, but isn't.
Scala 不能对任意尾调用进行尾调用优化,只能对那些可以转换为循环的尾调用进行优化(即当函数调用自身,而不是其他函数时).
Scala cannot make tailcall optimizations for arbitrary tail calls, only for those it can transform into loops (i.e. when the function calls itself, not some other function).
这篇关于是否可以使用延续使 foldRight 尾递归?的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!