Lazy Quicksort в Scala

Question

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

Answer 1

Да!

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

Answer 2

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