algorithm - F# 错误和归并排序

Question

我正在用 F# 编写合并排序函数，但收到此错误代码，我不明白为什么。

“错误 FS0030:值限制。值‘it’已被推断为具有泛型类型val it : '_a list when '_a : 比较要么将“它”定义为一个简单的数据项，使其成为一个带有显式参数的函数，或者，如果您不希望它成为通用的，请添加一个类型注释。”

我在尝试调用时收到错误代码，例如，mergesort [1; 2; 3; 3; 2; 6];;

这是代码片段

let rec merge l =
  match l with
  | ([], 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 l =
  match l with
  | [] -> ([], [])
  | [a] -> ([a], [])
  | a::b::cs -> let (M,N) = split cs
                (a::M, b::N)

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

Answer 1

尝试了 VS2015 中的代码。该错误在 FSI 中重现，但如果我将其作为程序运行，该程序会因 StackOverflowException 而崩溃。

原来在mergesort

中有一个小错误

let rec mergesort l =
  match l with
  | [] 
  | [_] -> l // Without this case mergesort crashes with `StackOverflowException`
  | L -> let (M, N) = split L
    merge (mergesort M, mergesort N)

修复此错误在 FSI 中为我修复了它。我注意到 FSI 偶尔会显示错误的错误消息。似乎是其中一种情况。