Understanding F# Value Restriction Errors

Question

I don't understand how the Value Restriction in F# works. I've read the explanation in the wiki as well as the MSDN documentation. What I don't understand is:

1. Why, for example, this gives me a Value Restriction error (Taken from this question):

   let toleq (e:float<_>) a b = (abs ( a - b ) ) < e
   

   But ths doesn't:

   let toleq e (a:float<_>) b = (abs ( a - b ) ) < e
   

2. This is generalized all right...

   let is_bigger a b = a < b
   

   but this isn't (it is specified as int):

   let add a b = a + b
   

3. Why functions with implicit parameters generate Value Restriction:

   this:

   let item_count = List.fold (fun acc _ -> 1 + acc) 0
   

   vs this:

   let item_count l = List.fold (fun acc _ -> 1 + acc) 0 l
   

   (Mind you, if I do use this function in a code fragment the VR error will be gone, but then the function will be specified to the type I used it for, and I want it to be generalized)

How does it work?

(I'm using the latest F#, v1.9.6.16)

Answer 1

EDIT

Better/recent info is here: Keeping partially applied function generic

(original below)

I think a pragmatic thing here is not to try to understand this too deeply, but rather to know a couple general strategies to get past the VR and move on with your work. It's a bit of a 'cop out' answer, but I'm not sure it makes sense to spend time understanding the intracacies of the F# type system (which continues to change in minor ways from release to release) here.

The two main strategies I would advocate are these. First, if you're defining a value with a function type (type with an arrow '->'), then ensure it is a syntactic function by doing eta-conversion:

// function that looks like a value, problem
let tupleList = List.map (fun x -> x,x)
// make it a syntactic function by adding argument to both sides
let tupleList l = List.map (fun x -> x,x) l

Second, if you still encounter VR/generalizing problems, then specify the entire type signature to say what you want (and then 'back off' as F# allows):

// below has a problem...
let toleq (e:float<_>) a b = (abs ( a - b ) ) < e
// so be fully explicit, get it working...
let toleq<[<Measure>]'u> (e:float<'u>) (a:float<'u>) (b:float<'u>) : bool = 
    (abs ( a - b ) ) < e
// then can experiment with removing annotations one-by-one...
let toleq<[<Measure>]'u> e (a:float<'u>) b = (abs ( a - b ) ) < e

I think those two strategies are the best pragmatic advice. That said, here's my attempt to answer your specific questions.

1. I don't know.

2. '>' is a fully generic function ('a -> 'a -> bool) which works for all types, and thus is_bigger generalizes. On the other-hand, '+' is an 'inline' function which works on a handful of primitive types and a certain class of other types; it can only be generalized inside other 'inline' functions, otherwise it must be pinned down to a specific type (or will default to 'int'). (The 'inline' method of ad-hoc polymorphism is how the mathematical operators in F# overcome the lack of "type classes".)

3. This is the 'syntactic function' issue I discussed above; 'let's compile down into fields/properties which, unlike functions, cannot be generic. So if you want it to be generic, make it a function. (See also this question for another exception to this rule.)

Answer 2

Value restriction was introduced to address some issues with polymorphism in the presence of side effects. F# inherits this from OCaml, and I believe value restriction exists in all ML variants. Here's a few more links for you to read, besides the links you cited. Since Haskell is pure, it's not subjected to this restriction.

As for your questions, I think question 3 is truly related to value restriction, while the first two are not.

Answer 3

No one, including the people on the F# team, knows the answer to this question in any meaningful way.

The F# type inference system is exactly like VB6 grammar in the sense that the compiler defines the truth.

Unfortunate, but true.