Scala中的泛型类型推断 [英] Generic type inference in Scala

问题描述

我写了下面的代码，这在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（））=>首先
 case（List（），_）=>如果比较器（f.asInstanceOf [E]，s.asInstanceOf [E]）是第二个
的情况（f :: restFirst，s :: restSecond） 0 => f :: merge（restFirst，second）
 case（f :: restFirst，s :: restSecond）=> s :: merge（first，restSecond）
} 
 
 l match {
 case List（）=>返回l 
 case List（x）=>返回l 
 case _ => 
 val（first，second）= l.splitAt（l.length / 2）
 merge（sort（比较器）（first），sort（比较器）（second））
} 
 
 
 
 
 
 $ b这不是以下内容，更优雅的解决方案： 
 
 
  import scala.collection.immutable.List 
 
对象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（））=>首先
 case（List（），_）=>第二个
的情况（f :: restFirst，s :: restSecond）如果比较器（f，s）< 0 => f :: merge（restFirst，second）
 case（f :: restFirst，s :: restSecond）=> s :: merge（first，restSecond）
} 
 
 l match {
 case List（）=>返回l 
 case List（x）=>返回l 
 case _ => 
 val（first，second）= l.splitAt（l.length / 2）
 merge（sort（比较器）（first），sort（比较器）（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 ？
解决方案
这是我能想到的最烦人的Scala陷阱之一（也许在与运算符分号推理相关的问题之后） 。你是正确答案的三个字符。
 
 
 
问题是 merge 上的类型参数。它引入了一个新的 T ，它在 sort 上隐藏 T 类型参数C>。因此，编译器不知道 comparator 可以应用于新的 T 的实例。你可以通过剧组来控制它，这就是为什么你的第一个版本可以工作，但是否则它会将 T 看作是一张空白页。
 
 
 
只需写下 def merge（first：List [T]，... ，你就可以了。
 
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 ?
解决方案
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.

                        
这篇关于Scala中的泛型类型推断的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！