Почему ограничение значения происходит с функцией MergeSort?

Question

У меня очень простая реализация MergeSort в List.

/// 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 когда' _a: сравнение Либо определите 'xs' как простой термин данных, сделайте его функцией с явными аргументами или, если вы не собираетесь использовать его чтобы быть общим, добавьте аннотацию типа.

Почему это происходит? Какой простой способ это исправить?

Answer 1

Вы не обрабатываете особый случай списков с 1 элементом в mergeSort, Общий случай "слишком общий", чтобы вывести правильный тип. Как следствие, компилятор выводит слишком общий тип для функции (список 'a - список'> b), и результатом всегда является общий список (который не разрешен из-за ограничения значения).

Если вы исправите это так, тип будет правильно выведен как "список ->" список.

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