任何递归函数都可以转换为使用堆(而不是堆栈)来跟踪上下文。该过程称为trampolining http://en.wikipedia.org/wiki/Tail_recursion#Through_trampolining.
以下是如何使用 Scalaz 实现它。
object TrampolineUsage extends App {
import scalaz._, Scalaz._, Free._
def quickSort[T: Order](xs: List[T]): Trampoline[List[T]] = {
assert(Thread.currentThread().getStackTrace.count(_.getMethodName == "quickSort") == 1)
xs match {
case Nil =>
return_ {
Nil
}
case x :: tail =>
val (left, right) = tail.partition(_ < x)
suspend {
for {
ls <- quickSort(left)
rs <- quickSort(right)
} yield ls ::: (x :: rs)
}
}
}
val xs = List.fill(32)(util.Random.nextInt())
val sorted = quickSort(xs).run
println(sorted)
val (steps, sorted1) = quickSort(xs).foldRun(0)((i, f) => (i + 1, f()))
println("sort took %d steps".format(steps))
}
当然,您需要一个非常大的结构或一个非常小的堆栈才能解决非尾递归分而治之算法的实际问题,因为您可以处理堆栈深度为 N 的 2^N 个元素。
http://blog.richdougherty.com/2009/04/tail-calls-tailrec-and-trampolines.html http://blog.richdougherty.com/2009/04/tail-calls-tailrec-and-trampolines.html
UPDATE
scalaz.Trampoline
是(更)更通用的结构的一个特例,Free
。它定义为type Trampoline[+A] = Free[Function0, A]
。其实可以这样写quickSort
更一般地,因此它由中使用的类型构造函数参数化Free
。此示例展示了如何完成此操作,以及如何使用相同的代码使用堆栈、堆或并发进行绑定。
https://github.com/scalaz/scalaz/blob/scalaz-7/example/src/main/scala/scalaz/example/TrampolineUsage.scala https://github.com/scalaz/scalaz/blob/scalaz-seven/example/src/main/scala/scalaz/example/TrampolineUsage.scala