Scala中的惰性快速排序

Question

是否有可能在Scala中執行this類型的事情？

Answer 1

是的！

Scala支持「延遲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) 
}