scala - Scala 中的泛型类型推断

Question

我编写了以下代码，这实际上是 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) )
            }
        }
    }
}

这不是以下更优雅的解决方案：

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

哪个不编译，给我以下错误消息：

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)

为什么需要显式强制转换，因为基础类型是 T ？

Answer 1

这是我能想到的最烦人的 Scala 陷阱之一（可能是在与运算符的分号推断相关的问题之后）。你距离正确答案只有三个字符。

问题是类型参数 on merge。它引入了一个新T的阴影T类型参数sort。因此，编译器不知道comparator可以将其应用于该 new 的实例T。您可以通过演员来控制它，这就是您的第一个版本有效的原因，但否则它会将其T视为一张白纸。

只要写def merge(first: List[T], ...，你会没事的。