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

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

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


f# mergesort value-restriction
person pad    schedule 01.10.2012    source источник
comment
см. Конечные точки значения F # Ограничение   -  person Paolo Falabella    schedule 01.10.2012
comment
Когда я вставляю код в FSI, я не получаю сообщений об ошибках на F# 2.0 Interactive build 2.0.0.0   -  person John Palmer    schedule 01.10.2012
comment
@JohnPalmer: Конечно, нет. Попробуйте выполнить функцию на каком-то входе.   -  person pad    schedule 01.10.2012
comment
@PaoloFalabella: Спасибо, я в курсе статьи. Просто недоумеваю, почему это произошло в данном случае.   -  person pad    schedule 01.10.2012

Ответы (1)


arrow_upward
6
arrow_downward

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

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

let rec mergeSort = function
    | [] -> []
    | [x] -> [x]
    | xs -> let xs1, xs2 = split xs
            merge (mergeSort xs1) (mergeSort xs2)
person wmeyer    schedule 01.10.2012
comment
Это также объясняет сбои из-за нечетной длины ввода в исходном коде. - person John Palmer; 01.10.2012