How to implement tail-recursive quick sort in Scala

Question

I wrote a recursive version:

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 ?

Answer 1

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

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

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

UPDATE

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