为什么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#Interactive中的任何输入进行测试时:

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

我遇到了一个值限制错误:

错误FS0030:值限制.值'xs'被推断为具有泛型类型val xs:'_a list when'_a:比较将'xs'定义为简单数据项,使其成为具有显式参数的函数,或者,如果您不打算使用它要是通用的,添加一个类型注释.

为什么会这样？什么是解决它的简单方法？

Answer 1

您没有处理1元素列表的特殊情况mergeSort.一般情况是"过于笼统"以推断出正确的类型.因此,编译器为函数推断出一种过于通用的类型('list - >'b list),结果总是一个通用列表(由于值限制而不允许).

如果您像这样修复它,该类型将被正确推断为"列表 - >"列表.

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