Quicksort paresseux dans Scala

Question

Est-il possible de faire this genre de chose à Scala?

Answer 1

Oui! Scala prend en charge les "valses paresseuses" comme un moyen de reporter le calcul d'une valeur jusqu'à ce qu'il soit réellement utilisé. Une grande partie de la bibliothèque Scala 2.8 est capable de travailler avec des collections définies paresseusement.

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

Il peut être fait avec des vues aussi bien, mais il est lié à être beaucoup plus lent:

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