Perché la restrizione del valore avviene con la funzione MergeSort?

Question

Ho un semplice Mergesort implementazione sulla lista.

/// 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)

.

Ma ogni volta che ho provato a testare con qualsiasi ingresso in F # Interactive:

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

.

Ho riscontrato un errore di restrizione del valore:

.

Errore FS0030: restrizione del valore.Il valore 'XS' è stato dedotto a avere tipo generico VAL XS: '_ Elenco quando' _a: il confronto definito 'xs' come un semplice termine dei dati, renderlo una funzione con argomenti espliciti o, se Non intendi essere generico, aggiungi un tipo annotazione.

Perché succede?Cos'è un modo semplice per risolverlo?

Answer 1

Non stai maneggiando il caso speciale di elenchi di 1 elemento in mergeSort. Il caso generale è "troppo generale" per inferire il tipo giusto.Di conseguenza, il compilatore definisce un tipo troppo generico per la funzione ('un elenco ->' B list) e il risultato è sempre un elenco generico (che non è consentito a causa della restrizione del valore).

Se lo risolvi in questo modo, il tipo verrà dedotto correttamente come 'un elenco ->' 'un elenco.

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

.