1

リストに非常に単純なMergeSort実装があります。

/// Divide the list into (almost) equal halves
let rec split = function
    | [] -> [], []
    | [x] -> [x], []
    | x1::x2::xs -> let xs1, xs2 = split xs
                    x1::xs1, x2::xs2

/// Merge two sorted lists
let rec merge xs ys =
    match xs, ys with
    | [], _ -> ys
    | _, [] -> xs
    | x::xs', y::ys' when x <= y -> x::merge xs' ys
    | _, y::ys' -> y::merge xs ys' 

let rec mergeSort = function
    | [] -> []
    | xs -> let xs1, xs2 = split xs
            merge (mergeSort xs1) (mergeSort xs2)

しかし、F# Interactive で任意の入力をテストしようとすると、次のようになります。

let xs = mergeSort [1;4;3;2];;

値制限エラーが発生しました:

エラー FS0030: 値の制限。値 'xs' はジェネリック型 val を持つと推測されています xs : '_a list when '_a : comparison 'xs' を単純なデータ項として定義するか、明示的な引数を持つ関数にするか、意図しない場合はジェネリックにするには、型注釈を追加します。

なぜそれが起こるのですか？それを修正する簡単な方法は何ですか？

4

1 に答える 1

6

の 1 要素リストの特殊なケースを処理していませんmergeSort。一般的なケースは「一般的すぎる」ため、正しい型を推測できません。結果として、コンパイラは関数のジェネリック型が多すぎると推測し ('a リスト -> 'b リスト)、結果は常にジェネリック リストになります (値の制限により許可されません)。

このように直せば、「a list -> a list」と型が正しく推論されるようになります。

let rec mergeSort = function
    | [] -> []
    | [x] -> [x]
    | xs -> let xs1, xs2 = split xs
            merge (mergeSort xs1) (mergeSort xs2)
于 2012-10-01T11:06:29.227 に答える