Ленивый Quicksort в Scala

Question

Ленивый Quicksort в Scala

Действительно ли возможно сделать этот вид вещи в Scala?

5

scala lazy-evaluation quicksort

задан Community 23 May 2017 в 10:28

2 ответа

Другие вопросы по тегам:

scala lazy-evaluation quicksort

Похожие вопросы:

score 13 · Answer 1

def quicksort[A](xs: Stream[A])(implicit o: Ordering[A]): Stream[A] = {
  import o._ 
  if (xs.isEmpty) xs else {
      val (smaller, bigger) = xs.tail.partition(_ < xs.head)
      quicksort(smaller) #::: xs.head #:: quicksort(bigger)
  }
}

Это также можно сделать с представлениями, хотя это должно быть намного медленнее:

def quicksort[A](xs: List[A])(implicit o: Ordering[A]) = {
  import o._
  def qs(xs: SeqView[A, List[A]]): SeqView[A, Seq[_]] = if (xs.isEmpty) xs else {
    val (smaller, bigger) = xs.tail.partition(_ < xs.head)
    qs(smaller) ++ (xs.head +: qs(bigger))
  }
  qs(xs.view)
}

score 0 · Answer 2

Да!

Scala поддерживает «ленивые значения» как способ отложить вычисление значения до его фактического использования. Большая часть библиотеки Scala 2.8 способна работать с лениво определяемыми коллекциями.