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)

Rectory

Cross ref to another question on same topic: #417008 – Milli

Just as an update to this - case (1) was likely a bug, as it doesn't produce the error anymore. – Disagreeable

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.)

Maccabean

Dmitri has written a nice post on this more recently: blogs.msdn.com/b/mulambda/archive/2010/05/01/… – Maccabean

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.

Unit

Yes. OCaml has a relaxed value restriction where it allows non-generalized type variables at the top-level in the REPL where they are displayed as '_a rather than 'a. The latter means the code is polymorphic and works for all types 'a whereas the former means the code is monomorphic in this type and works only for one specific type '_a and that has not yet been determined. This is made easier by the fact that OCaml uses a uniform data representation for all polymorphic data. It would be harder in F# because reified generics need the exact monomorphic type to be known at compilation. – Mata

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.

Funiculate

Well, I bet Don knows the answer. And F# is still in Beta. At some point we'll have to firm up the spec. And the compiler is not a black box; the F# compiler source is freely available. All that said, I didn't downvote you, as for the most part I don't disagree (hardly anyone 'knows', and the lack of a succinct spec is indeed unfortunate). – Maccabean

Every language has its nooks and crannies. F# for the most part is a very stable, very elegant & practical language (IMHO). Obviously, it is still work in progress, but compared to some other developing languages (without naming names) the future sure is bright for F#. That said, I didn't downvote you either. – Rectory

@Maccabean Don knows the answer only because he has access to the source. There is no "theory" of type inference in F#. – Funiculate

@Dave Berk I think that F# is a beautiful language. In fact, I run an F# user group. However, it doesn't follow that it has a beautiful type inference mechanism. – Funiculate

@Maccabean is this still true today (2014)? that the F# type inference is tricky and only defined by the source itself? would you still answer "I don't know" to the first question? – Rufford

I find these all these assertions about F#'s type inference strange. The value restriction is there to handle the case of a non-generalized type variable escaping to the top-level. – Mata