Una clasificación rápida genérica en Scala

Question

He estado jugando con Scala recientemente y estaba pensando acerca de cómo implementar una versión genérica de la clasificación rápida en el mismo (sólo para obtener una mejor sensación para el idioma)

me ocurrió algo como esto

object Main { 
    def qs[T](a: List[T], f: (T, T) => Boolean): List[T] = { 
    if (a == Nil) return a 
    val (l, g) = a drop 1 partition (f(a(0),(_:T))) 
    qs(l, f) ::: List(a(0)) ::: qs(g, f) 
    } 

    def main(args: Array[String]): Unit = { 
    val a = List(5,3,2,1,7,8,9,4,6) 
    val qsInt = qs(_: List[Int], (_: Int) > (_: Int)) 
    println(qsInt(a)) 
    } 

} 

esto no es tan genérico como yo quería que fuera, ya que tengo que indicar explícitamente cómo ordenar los elementos en lugar de simplemente hacer algo como

val (l, g) = a drop 1 partition (a(0) >) 

¿Cómo puedo decirle al compilador que T solo necesita implementar el operador mayor que para poder ordenar esta función?

Saludos

Answer 1

def qsort[T <% Ordered[T]](list: List[T]): List[T] = { 
    list match { 
    case Nil => Nil  
    case x::xs =>   
    val (before, after) = xs partition (_ < x) 
    qsort(before) ++ (x :: qsort(after)) 
    } 
} 

Answer 2

Desde Rogercovered el caso Ordered, permítanme cubrir Ordering:

def qsort[T](list: List[T])(implicit ord: Ordering[T]): List[T] = list match { 
    // import ord._ // enables "_ < x" syntax 
    case Nil => Nil 
    case x :: xs => 
    val (before, after) = xs partition (ord.lt(_, x)) 
    qsort(before) ::: x :: qsort(after) 
} 

Usando Ordering tiene dos ventajas principales:

1. El tipo T no necesita tener abeja n creado como Ordered.
2. Uno puede proporcionar fácilmente pedidos alternativos.

Por ejemplo, en la Scala 2.8:

def sortIgnoreCase(strs: List[String]) = { 
    val myOrdering = Ordering.fromLessThan { (x: String, y: String) => 
    x.toLowerCase < y.toLowerCase 
    } 
    qsort(strs)(myOrdering) 
}