是否有可能使用continuation来使foldRight尾部递归？
以下博客文章展示了如何在F＃ foldBack中使用延续传递样式进行尾递归。
在斯卡拉这意味着：
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
}
}
可以通过这样做使尾部递归：
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)
}
不幸的是，我仍然对长列表产生堆栈溢出。 循环是尾递归和优化，但我想栈积累只是进入继续调用。
为什么这不是F＃的问题？ 有什么方法可以用Scala解决这个问题吗？
编辑：这里有一些代码显示了堆栈的深度：
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)))本身。 应该对整个业务进行尾调优化，但不是。
对于任意的尾调用，Scala不能对任意尾调用进行tailcall优化，只能对那些可以转换成循环的调用（即当函数调用自身而不是其他函数时）进行尾调用。
Jon，nm，谢谢你的回答。 根据你的意见，我想我会尝试和使用蹦床。 一些研究表明，Scala在TailCalls支持蹦床。 这是我在摆弄了一下之后想到的：
def foldContTC[T,U](list: List[T], acc: U)(f: (T, U) => U): U = {
import scala.util.control.TailCalls._
@annotation.tailrec
def loop(l: List[T], k: (U) => TailRec[U]): TailRec[U] = {
l match {
case x :: xs => loop(xs, (racc => tailcall(k(f(x, racc)))))
case Nil => k(acc)
}
}
loop(list, u => done(u)).result
}
我很感兴趣的是看看这个方案与没有蹦床的解决方案以及默认的foldLeft和foldRight实现相比如何。 以下是基准代码和一些结果：
val size = 1000
val list = List.fill(size)(1)
val warm = 10
val n = 1000
bench("foldContTC", warm, lots(n, foldContTC(list, 0)(_ + _)))
bench("foldCont", warm, lots(n, foldCont(list, 0)(_ + _)))
bench("foldRight", warm, lots(n, list.foldRight(0)(_ + _)))
bench("foldLeft", warm, lots(n, list.foldLeft(0)(_ + _)))
bench("foldLeft.reverse", warm, lots(n, list.reverse.foldLeft(0)(_ + _)))
时间是：
foldContTC: warming...
Elapsed: 0.094
foldCont: warming...
Elapsed: 0.060
foldRight: warming...
Elapsed: 0.160
foldLeft: warming...
Elapsed: 0.076
foldLeft.reverse: warming...
Elapsed: 0.155
基于此，看起来蹦床实际上表现出相当不错的表现。 我怀疑在拳击/拆箱之前的处罚相对没那么糟糕。
编辑：如Jon的评论所建议的，这里是1M项目的时间表，这些项目确认性能会随着更大的列表而降低。 另外我发现库List.foldLeft实现没有被覆盖，所以我使用下面的foldLeft2来计时：
def foldLeft2[T,U](list: List[T], acc: U)(f: (T, U) => U): U = {
list match {
case x :: xs => foldLeft2(xs, f(x, acc))(f)
case Nil => acc
}
}
val size = 1000000
val list = List.fill(size)(1)
val warm = 10
val n = 2
bench("foldContTC", warm, lots(n, foldContTC(list, 0)(_ + _)))
bench("foldLeft", warm, lots(n, list.foldLeft(0)(_ + _)))
bench("foldLeft2", warm, lots(n, foldLeft2(list, 0)(_ + _)))
bench("foldLeft.reverse", warm, lots(n, list.reverse.foldLeft(0)(_ + _)))
bench("foldLeft2.reverse", warm, lots(n, foldLeft2(list.reverse, 0)(_ + _)))
收益率：
foldContTC: warming...
Elapsed: 0.801
foldLeft: warming...
Elapsed: 0.156
foldLeft2: warming...
Elapsed: 0.054
foldLeft.reverse: warming...
Elapsed: 0.808
foldLeft2.reverse: warming...
Elapsed: 0.221
所以foldLeft2.reverse是赢家......
为什么这不是F＃的问题？
F＃已经优化了所有尾部调用。
有什么方法可以用Scala解决这个问题吗？
您可以使用其他技术（如蹦床）来完成TCO，但您会失去互操作性，因为它会改变调用约定，速度会降低10倍。 这是我不使用Scala的三个原因之一。
编辑
你的基准测试结果表明Scala的蹦床比我上次测试它们要快得多。 此外，使用F＃和更大的列表添加等效基准很有意思（因为在小列表上进行CPS没有意义！）。
对于笔记本电脑上1.67GHz N570 Intel Atom笔记本电脑上1,000个元素列表中的1,000倍，我得到：
List.fold 0.022s
List.rev+fold 0.116s
List.foldBack 0.047s
foldContTC 0.334s
对于1x 1,000,000元的列表，我得到：
List.fold 0.024s
List.rev+fold 0.188s
List.foldBack 0.054s
foldContTC 0.570s
您可能还会对在关于使用优化的尾递归函数取代OCaml的非尾递归列表函数的上下文中关于caml-list的旧讨论感兴趣。
链接地址: http://www.djcxy.com/p/80527.html上一篇: Is it possible to use continuations to make foldRight tail recursive?