Как реализовать хвостовую рекурсивную быструю сортировку в Scala

Question

Я написал рекурсивную версию:

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

Но я не знаю, как превратить его в рекурсивный. Кто-нибудь может дать мне предложение?

Answer 1

Любая рекурсивная функция может быть преобразована для использования кучи, а не стека, для отслеживания контекста. Процесс называется 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.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-seven/example/src/main/scala/scalaz/example/TrampolineUsage.scala

Answer 2

Хвостовая рекурсия требует, чтобы вы проходили работу, как завершенную, так и рабочую, вперед на каждом шаге.Так что вам просто нужно инкапсулировать свою работу в кучу, а не в стек.Вы можете использовать список как стек, так что это достаточно просто.Вот реализация:

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

Это, конечно, просто особый случай прыжка на батуте, связанный с ретронимом (когда вам не нужно передавать функцию вперед).К счастью, этот случай достаточно легко сделать вручную.

Answer 3

Я только что написал эту статью, которая содержит пошаговые инструкции о том, как преобразовать классическую реализацию быстрой сортировки в хвостовую рекурсивную форму:

Быстрая сортировка переписана в хвостовой рекурсивной форме - пример в Scala

Надеюсь, вам будет интересно!