是否可以使用延续使 foldRight 尾递归?

本文介绍了是否可以使用延续使 foldRight 尾递归?的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

以下博客文章展示了如何在 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).