以下博客文章显示了如何在F#中设置为尾递归.
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尾递归?
发布评论