如何在Scala中实现尾递归快速排序 [英] How to implement tail-recursive quick sort in Scala

问题描述

我写了一个递归版本：

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)
}

但是我不知道如何将它改成尾部复发。有人可以给我一个建议吗？

But I don't know how to change it into tail-recurisive. Can anyone give me a suggestion ?

推荐答案

任何递归函数都可以转换为使用堆而不是堆栈来跟踪上下文。该过程称为 trampolining 。

Any recursive function can be be converted to use the heap, rather than the stack, to track the context. The process is called trampolining.

以下是使用Scalaz实现的方法。

Here's how it could be implemented with 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个元素。

Of course, you need either a really big structure or a really small stack to have a practical problem with a non-tail-recursive divide and conquer algorithm, as you can handle 2^N elements with a stack depth of N.

http://blog.richdougherty.com/2009/04/tail-calls-tailrec-and -trampolines.html

更新

scalaz.Trampoline 是一个特别的例子， ，免费。它被定义为 type Trampoline [+ A] = Free [Function0，A] 。实际上可以更一般地写入 quickSort ，所以它是由 Free 中使用的类型构造函数进行参数化的。此示例显示了如何完成此操作，以及如何使用相同的代码使用堆栈，堆或并发进行绑定。

scalaz.Trampoline is a special case of a (much) more general structure, Free. It's defined as type Trampoline[+A] = Free[Function0, A]. It's actually possible to write quickSort more generically, so it is parameterized by the type constructor used in Free. This example shows how this is done, and how you can then use the same code to bind using the stack, the heap, or in concurrently.

https://github.com/scalaz/ scalaz / blob / scalaz-seven / example / src / main / scala / scalaz / example / TrampolineUsage.scala

这篇关于如何在Scala中实现尾递归快速排序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！