Lazy Quicksort en Scala

Question

¿Es posible hacer this tipo de cosa en Scala?

Answer 1

Sí!

Scala admite "lazy vals" como una forma de diferir el cálculo de un valor hasta que realmente se use. Gran parte de la biblioteca de Scala 2.8 es capaz de trabajar con colecciones definidas de forma diferida.

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

Se puede hacer con vistas a su vez, a pesar de que está destinado a ser mucho más lento:

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