왜 가치 제한이 합병 함수로 일어나는가?

Question

나는 매우 간단한

/// 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 목록'_a : 비교 'xs'를 간단한 데이터 용어로 정의하고, 명시 적 인수가있는 함수로 만들거나 일반적으로 주석을 추가하는 것이 좋지 않아야합니다.

왜 그것이 일어날까요?그것을 고치는 간단한 방법은 무엇입니까?

Answer 1

mergeSort의 1 요소 목록의 특수한 경우를 처리하지 않습니다. 일반적인 경우는 올바른 유형을 추론하기 위해 "너무 일반"입니다.결과적으로 컴파일러는 함수 ( '목록 -> b 목록)에 대한 너무 제네릭 유형이고 결과는 항상 일반 목록 (값 제한으로 인해 허용되지 않음)입니다.

이렇게 해결하면 유형이 'A 목록 ->'목록으로 올바르게 추론됩니다.

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

.