Generic type inference in Scala
generics, scala, type-inference
Solution
This is one of the most annoying Scala gotchas I can think of (maybe after semicolon inference-related issues with operators). You're three characters from the correct answer.
The problem is the type parameter on `merge`. It introduces a new `T` that shadows the `T` type parameter on `sort`. The compiler therefore doesn't know that `comparator` can be applied to instances of that new `T`. You can boss it around with a cast, which is why your first version works, but otherwise it sees that `T` as a blank slate.
Just write `def merge(first: List[T], ...` and you'll be fine.
Problem
I've written the following code, which is actually a dumb merge-sort implementation in scala: ``` import scala.collection.immutable.List object MergeSort { def sort[T,E]( comparator: (E,E) => Int ) (l: List[T]): List[T] = { def merge[T](first: List[T], second: List[T]): List[T] = (first, second) match { case (_, List()) => first case (List(), _) => second case (f::restFirst, s::restSecond) if comparator(f.asInstanceOf[E],s.asInstanceOf[E]) < 0 => f :: merge(restFirst, second) case (f::restFirst, s::restSecond) => s :: merge(first, restSecond) } l match { case List() => return l case List(x) => return l case _ => { val (first, second) = l.splitAt( l.length / 2 ) merge( sort(comparator)(first), sort(comparator)(second) ) } } } } ``` This is instead of the following, more elegant, solution: ``` import scala.collection.immutable.List object MergeSort { def sort[T]( comparator: (T,T) => Int ) (l: List[T]): List[T] = { def merge[T](first: List[T], second: List[T]): List[T] = (first, second) match { case (_, List()) => first case (List(), _) => second case (f::restFirst, s::restSecond) if comparator(f,s) < 0 => f :: merge(restFirst, second) case (f::restFirst, s::restSecond) => s :: merge(first, restSecond) } l match { case List() => return l case List(x) => return l case _ => { val (first, second) = l.splitAt( l.length / 2 ) merge( sort(comparator)(first), sort(comparator)(second) ) } } } } ``` Which doesn't compile, giving me the following error message: ``` MergeSort.scala:10: type mismatch; [error] found : f.type (with underlying type T) [error] required: T [error] case (f::restFirst, s::restSecond) if comparator(f,s) < 0 => f :: merge(restFirst, second) ``` Why is the explicit cast necessary since the underlying type is T ?