Mergesort получает ошибку в F#

Question

let rec merge = function
| ([], ys) -> ys
| (xs, []) -> xs
| (x::xs, y::ys) -> if x < y then x :: merge (xs, y::ys)
                    else y :: merge (x::xs, ys)

let rec split = function
| [] -> ([], [])
| [a] -> ([a], [])
| a::b::cs -> let (M,N) = split cs
              (a::M, b::N)

let rec mergesort = function
| [] -> []
| L -> let (M, N) = split L
       merge (mergesort M, mergesort N)


mergesort [5;3;2;1]  // Will throw an error.

Я взял этот код отсюда Stackru Вопрос, но когда я запускаю сортировку слиянием со списком, я получаю сообщение об ошибке:

stdin(192,1): error FS0030: Value restriction. The value 'it' has been inferred to have generic type
    val it : '_a list when '_a : comparison 

Как бы я исправить эту проблему? В чем проблема? Чем больше информации, тем лучше (чтобы я мог учиться:))

Answer 1

В вашей функции сортировки слиянием отсутствует регистр, в результате чего компилятор выводит сигнатуру 'a list -> 'b list вместо 'a list -> 'a list что это должно быть. Причина должна быть 'a list -> 'a list в том, что вы не хотите менять тип списка в mergesort.

Попробуйте изменить функцию слияния на это, это должно решить проблему:

let rec mergesort = function
 | [] -> []
 | [a] -> [a]
 | L -> let (M, N) = split L
        merge (mergesort M, mergesort N)

Однако другая проблема с вашим кодом заключается в том, что ни слияние, ни разделение не являются хвостовыми рекурсиями, и поэтому вы получите исключения переполнения стека в больших списках (попробуйте вызвать исправленную сортировку слиянием следующим образом mergesort [for i in 1000000..-1..1 -> i]).

Вы можете сделать свои функции разделения и слияния хвостовыми рекурсивными, используя шаблон аккумулятора

let split list =
  let rec aux l acc1 acc2 =
    match l with
        | [] -> (acc1,acc2)
        | [x] -> (x::acc1,acc2)
        | x::y::tail ->
            aux tail (x::acc1) (y::acc2)
  aux list [] []

let merge l1 l2 = 
  let rec aux l1 l2 result =
    match l1, l2 with
    | [], [] -> result
    | [], h :: t | h :: t, [] -> aux [] t (h :: result)
    | h1 :: t1, h2 :: t2 ->
        if h1 < h2 then aux t1 l2 (h1 :: result)
        else            aux l1 t2 (h2 :: result)
  List.rev (aux l1 l2 [])

Вы можете прочитать больше о шаблоне аккумулятора здесь; примеры приведены на языке lisp, но это общий шаблон, который работает на любом языке, который обеспечивает оптимизацию хвостовых вызовов.