Edit I've left the original post here, but have a much simpler reproduction below.
I've been working through a tutorial on F# and I'm at a section where we're implementing a basic mergesort. The first component is to build a split function to turn a list into a 2-tuple of lists formed by splitting the input.
I spent a while on my own and searched online before turning to the tutorial solutions. Everything that I've found fails when splitting and empty list, with the same error.
error FS0030: Value restriction. The value 'it' has
been inferred to have generic type
val it : '_a list * '_a list
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
All the functions I can come up with and find have a type signature as follows which seems right (some of the samples take an argument for the point at which to split but can be refactored to this)
val split : list:'a list -> 'a list * 'a list
The error makes it clear that this is something to do with types, but I am clueless at this point. Is it possible in F# to make a well-behaved split function that returns a 2-tuple of empty lists when passed a single empty list?
Would the better solution be to define a type to restrict the domain of split to only be non-empty lists?
Here are some of the things I've tried, and all fail in the same way when called as follows
split []
My own version
let split (list : 'a list) =
let rec s count head tail =
match (count, head, tail) with
| (0, [], []) -> [], []
| (0, head, tail) -> List.rev head, tail
| (n, head, x :: tail) -> s (n - 1) (x :: head) tail
s (list.Length / 2) [] list
Two from the tutorial:
let rec split = function
| [] -> ([], [])
| [a] -> ([a], [])
| a::b::cs -> let (r, s) = split cs
in (a::r, b::s)
let split list = List.fold (fun (a,b) c -> (b, c::a)) ([], []) list
A version using List.take and List.skip:
let split (list : 'a list) =
let n = list.Length / 2
List.take n list, List.skip n list
Edit update below
I've finished up writing the rest of my mergesort and I get a similar error when calling this on an empty list as well.
// list: 'a list -> 'a list when 'a : comparison
let rec msort list =
match list with
| [] -> []
| [x] -> [x]
| x::xs ->
let head, tail = split (x::xs)
in merge (msort head, msort tail)
When called on the empty list this gives the same error above. The split function isn't even reached in this case.
msort []
lists.fsx(2252,1): 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.
This made me more curious as it seems like a function with a signature that includes 'a list -> 'a list doesn't work well with an empty list input.
My minimum viable reproduction follows:
> List.map (fun x -> x) [];;
lists.fsx(2270,1): error FS0030: Value restriction. The
value 'it' has been inferred to have generic type
val it : '_a list
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.
> List.map (fun x -> x + 1) [];;
val it : int list = []
So something is different between a function expecting a specifically typed empty list and something expecting a generically typed empty list.
Can anyone help explain what I (and many examples I can find) are doing wrong in the splitting function above, or explain what's happening in the types that makes an empty typed list behave differently than an empty generically typed list?
