我写了一个递归的版本。
def quickSort[T](xs: List[T])(p: (T, T) => Boolean): List[T] = xs match{
case Nil => Nil
case _ =>
val x = xs.head
val (left, right) = xs.tail.partition(p(_, x))
val left_sorted = quickSort(left)(p)
val right_sorted = quickSort(right)(p)
left_sorted ::: (x :: right_sorted)
}
但我不知道怎么把它改成尾部递归式的。谁能给我一个建议?
任何递归函数都可以被转换为使用堆而不是栈来跟踪上下文。这个过程被称为 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))
}
当然,你需要一个非常大的结构或者非常小的堆栈,才能用非尾部递归的分而治之算法解决实际问题,因为你可以处理2^N个元素,堆栈深度为N。
http:/blog.richdougherty.com200904tail-calls-tailrec-and-tampolines.html。
更新
scalaz.Trampoline
是一个(更)一般的结构的特例。Free
. 它的定义是 type Trampoline[+A] = Free[Function0, A]
. 其实可以写 quickSort
更为通用,所以它的参数化是在 Free
. 这个例子展示了如何做到这一点,以及如何使用相同的代码来使用堆栈、堆或并发地进行绑定。
https:/github.comscalazscalazblobscalaz-sevenexamplesrcmainscalascalazexampleTrampolineUsage.scala。
尾部递归要求你在每一步都要向前传递工作,包括已完成的和待做的工作。 所以你只需要把你的待做工作封装在堆上,而不是堆上。 你可以使用一个列表作为堆栈,所以这很简单。 下面是一个实现。
def quicksort[T](xs: List[T])(lt: (T,T) => Boolean) = {
@annotation.tailrec
def qsort(todo: List[List[T]], done: List[T]): List[T] = todo match {
case Nil => done
case xs :: rest => xs match {
case Nil => qsort(rest, done)
case x :: xrest =>
val (ls, rs) = (xrest partition(lt(x,_)))
if (ls.isEmpty) {
if (rs.isEmpty) qsort(rest, x :: done)
else qsort(rs :: rest, x :: done)
}
else qsort(ls :: List(x) :: rs :: rest, done)
}
}
qsort(List(xs),Nil)
}
当然,这只是trampolining的一种特殊情况,就像重名所链接的那样(在这里你不需要向前传递函数)。 幸运的是,这种情况很容易手工完成。
还有一个版本使用了尾数记录、模式匹配和隐式排序。
def sort[T](list: List[T])(implicit ordering: Ordering[T]): List[T] = {
@scala.annotation.tailrec
def quickSort(todo: List[List[T]], accumulator: List[T]): List[T] = todo match {
case Nil => accumulator
case head :: rest => head match {
case Nil => quickSort(rest, accumulator)
case pivot :: others =>
others.partition(ordering.lteq(_, pivot)) match {
case (Nil, Nil) => quickSort(rest, pivot :: accumulator)
case (Nil, larger) => quickSort(larger :: rest, pivot :: accumulator)
case (smaller, larger) => quickSort(smaller :: List(pivot) :: larger :: rest, accumulator)
}
}
}
quickSort(List(list), Nil)
}
val sorted = sort(someValues)
val reverseSorted = sort(someIntValues)(Ordering[Int].reverse)