9

私は次のコードを書きました。これは実際には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であるため、明示的なキャストが必要なのはなぜですか？

4

1 に答える 1

13

これは、私が考えることができる最も厄介なScalaの落とし穴の1つです（おそらく、演算子に関するセミコロン推論関連の問題の後）。あなたは正解から3人のキャラクターです。

問題は、のタイプパラメータmergeです。のtypeパラメータTをシャドウする新しいものが導入されています。したがって、コンパイラは、それがその新しいのインスタンスに適用できることを知りません。キャストでボスを付けることができます。これが最初のバージョンが機能する理由ですが、それ以外の場合は白紙の状態と見なされます。TsortcomparatorTT

書くだけdef merge(first: List[T], ...で大丈夫です。

于 2012-12-11T23:42:31.387 に答える