0 
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.

我从这里StackOverflow Question获取了这段代码，但是当我使用列表运行合并排序时出现错误：

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

我将如何解决这个问题？问题是什么？信息越多越好（所以我可以学习:)）

4

1 回答 1

3

您的 mergesort 函数缺少一个案例，导致编译器推断签名'a list -> 'b list而不是'a list -> 'a list它应该是的。原因应该'a list -> 'a list是您不希望更改合并排序中列表的类型。

尝试将您的合并排序功能更改为此，这应该可以解决问题：

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 中，但它是一种通用模式，适用于任何提供尾调用优化的语言。

于 2013-05-30T06:23:34.923 回答