F# Error and Mergesort

Question

I'm writing a mergesort function in F#, but I am receiving this error code and I don't understand why.

"error FS0030: Value restriction. The value 'it' has been inferred to have generic type val it : '_a list when '_a : comparison Either define 'it' as a simple data term, make it a function with explicit arguments or, if you do not intend for it to be generic, add a type annotation."

I get the error code when I try calling, for example, mergesort [1; 2; 3; 3; 2; 6];;

Here is the code snippet

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)

For me the code compiles fine although there seems to be a slight mistake in mergesort causing stackoverflow. By fixing it one seem to fix the FSI problem. FSI occassionally reports the wrong error, seems like it's one of those cases. — Just another metaprogrammer

Just another metaprogrammer Just another metaprogrammer · Accepted Answer · 2016-01-30T13:47:48

Tried the code in VS2015. The error reproduces in FSI but if I run it as a program the program crashes with StackOverflowException.

Turns out there's a slight mistake in 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)

Fixing this error fixed it for me in FSI. I have noticed that occassionally FSI shows the wrong error message. Seems to be one of those cases.

F# Error and Mergesort

1 Answers