I've been playing around with Scala recently and was thinking about how to implement a generic version of quicksort in it (just to get a better feeling for the language)
I came up with something like this
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))
}
}
This is not as generic as I wanted it to be, since I have to explicitly state how to order the elements rather then just doing something like
val (l, g) = a drop 1 partition (a(0) >)
How开发者_StackOverflow社区 can I tell the compiler that T only needs to implement the greater-than operator to be sortable by this function?
Regards
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))
}
}
Since Roger covered the Ordered
case, let me cover 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)
}
Using Ordering
has two main advantages:
- The
T
type does not need to have been created asOrdered
. - One can easily provide alternate orderings.
For instance, on Scala 2.8:
def sortIgnoreCase(strs: List[String]) = {
val myOrdering = Ordering.fromLessThan { (x: String, y: String) =>
x.toLowerCase < y.toLowerCase
}
qsort(strs)(myOrdering)
}
精彩评论