CODEWITHSUNDEEP
typesf#
Worice
Worice

Reputation: 4037

Value limitation and type inference

I built a simple function that, given a list, returns a list where the contiguous occurrences of an elements in the input are reduced to one.

let rec reduce l =
match l with
| []                ->  []
| [x]               ->  [x]
| x::(y::_ as xs)   ->  if x = y then
                            reduce xs
                        else
                            x::(reduce xs)


# reduce [1;1;2;2;2;3;3;4;3;3;3];;
- : int list = [1;2;3;4;3].
# reduce [’a’;’a’;’a’;’b’];;
- : char list = [’a’; ’b’].
# reduce [];;                // The case 
- : ’a list = []

Everything work as expected, except for the empty list [] input. The complainer says error FS0030: Value restriction. I tried to get a better comprehension of the phenomena through the documentation, but I feel like I still do not possess the skills to get the point properly. Why a generic function does need the case with [] to be type specified? Could not the result [] being simply reported without type inference? And, finally, how the function should be structured, in order to menage such a case?

Upvotes: 1

Views: 59

Answers (1)

Tomas Petricek
Tomas Petricek

Reputation: 243041

As John said in the comment, the problem is that [] does not give the compiler any hint about what the type of the list is - in all other cases, you know it's a list of characters of integers, but here, the type is not known.

You cannot run F# code that involves unknown generic types, so there is no way to run your code and get a generic list back - when running code, all types need to be fully specified.

You can provide a type annotation in a number of ways to fix the type:

reduce ([] : int list)
(reduce [] : int list)
(reduce:int list -> _) []

You could also wrap the call into another generic function, which compiles, because now the generic code is inside another generic function that requires a type in order to be used:

let foo () = reduce []

But now you have the same problem - you need to specify type when calling foo, or the compiler needs to be able to infer it from context, e.g. if you write 1 :: foo()

Upvotes: 2

Related Questions