Ogólny quicksort w Scala

Question

Grałem około z Scala niedawno i myślał o tym, jak wdrożyć generycznej wersji quicksort w nim (tak, aby uzyskać lepsze wyczucie języka)

wymyśliłem coś takiego

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

} 

to nie jest tak jak chciałem generic to być, ponieważ muszę jednoznacznie stwierdzić, jak zamówić elementy, a następnie po prostu robi coś

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

Jak mogę powiedzieć kompilatorowi, że T potrzebuje tylko operatora większego niż do sortowania według tej funkcji?

Pozdrowienia

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

Od Rogercovered przypadek Ordered, niech pokrycie 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) 
} 

Korzystanie Ordering ma dwie główne zalety:

1. Typ T nie potrzebują mieć pszczołę n utworzone jako Ordered.
2. Można łatwo zapewnić alternatywne zamówienia.

Na przykład, na Scala 2.8:

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