Operator < doesn't seem to support "Any" type How to fix it?

1
votes

The following is a quick-sort function written in Scala to sort a list of mixed types(int, double, float etc.). The error popped out and said in line 3 "Type mismatch, expected: T => Boolean, actual: T => Any Cannot resolve symbol <". How do I fix this?

The Intellij IDE running on Windows 10 gave this error message. 


    def qsort[T](list: List[T]): List[T] = list match {
      case Nil => Nil
      case pivot :: tail =>
        val(smaller, rest) = tail.partition(_ < pivot)
        qsort(smaller) ::: pivot :: qsort(rest)
    }
2
scalagenericsoperator-overloading
How would you compare arbitrary types? T needs to be a Comparable type if you want to compare it. – Carcigenicate
In C++, comparable types don't not need to be specified as long as they have operator < <= etc. But i am not familiar with the mechanism in Scala. – user132603
C++ checks for < etc. when you call the generic function, but Scala does this check when it compiles the function. Scala needs to be sure it will work for all possible T, so you need to restrict the allowable types somehow. You can restrict the type itself, or add an implicit parameter. – Tim

2 Answers

1
votes

Dmytro's answer will work for any type that can be implicitly converted to Ordered[T]. This is a bit peculiar, and in idiomatic Scala, people often prefer to use an implicit Ordering instead. This way, the order is completely separated from the implementation of T.

def qsort[T : Ordering](list: List[T]): List[T]

The signature uses a context-bound, and [T: Ordering] is syntactic sugar for the more verbose

def qsort[T](list: List[T])(implicit ev: Ordering[T]): List[T]

If you come from Java, Ordering is to Ordered what Comparator is to Comparable. Note that Ordering[T] is in spirit very similar to T => Ordered[T], but I think it is simpler to wrap your head around when you're a beginner. It also gives you a nice set of methods to create and manipulate Orderings.

Finally, note that using List for a sorting method like quick sort will result in really poor performances, because appending to a List is O(n). If performance is a concern, use an Array with an in-place implementation of quicksort.

0
votes

Add implicit parameter

def qsort[T](list: List[T])(implicit ev: T => Ordered[T]) = ...