MergeSort函數爲什麼會發生數值限制？

Question

我在List上有一個非常簡單的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＃互動任何輸入測試：

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

我遇到了一個值限制錯誤：

error FS0030: Value restriction. The value 'xs' has been inferred to have generic type val xs : '_a list when '_a : comparison Either define 'xs' as a simple data term, make it a function with explicit arguments or, if you do not intend for it to be generic, add a type annotation.

它爲什麼會發生？什麼是解決它的簡單方法？

Answer 1

您無法處理mergeSort中1元素列表的特殊情況。 一般情況下，「太籠統」來推斷正確的類型。因此，編譯器推斷函數的泛型類型（'a list - >'b list），結果總是一個通用列表（由於值限制，這是不允許的）。

如果你像這樣修復它，類型將被正確地推斷爲'列表 - >'列表。

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