Understanding F# value restriction

Question

I'm learning F#. I'm here because I had something hard to understand about value restriction.

Here are the examples from the book I'm studying with.

let mapFirst = List.map fst

Since I had learned FP with haskell, I was pretty sure that this code would be well compiled, but it was not the case. It resulted error FS0030 (Sorry that I can't copy-paste fsi error message, since it was written in korean). Instead, I had to provide an explicit argument like:

let mapFirst inp = List.map fst inp   // or inp |> List.map fst

But why? I thought that with the above example, compiler can surely infer the type of given value:

val mapFirst : ('a * 'b) list -> 'a list

If I remind correctly, I called this thing in haskell eta-conversion, and above two examples are entirely identical. (Maybe not entirely, though). Why should I privide parameters explicitly to the function can be curried without any loss of information?

I've understood that something like

let empties = Array.create 100 []

will not compile and why, but I don't think It has something to do with my question.

※ I took a look on this question, but it did not help.

Answer 1

This has to do with mutability.

Consider this snippet:

type T<'a> = { mutable x : 'a option }

let t = { x = None }

The type of t is T<'a> - that is, t is generic, it has a generic parameter 'a, meaning t.x can be of any type - whatever the consumer chooses.

Then, suppose in one part of the program you do:

t.x <- Some 42

Perfectly legitimate: when accessing t you choose 'a = int and then t.x : int option, so you can push Some 42 into it.

Then, suppose in another part of your program you do:

t.x <- Some "foo"

Oh noes, what happens now? Is t.x : int option or is it string option? If the compiler faithfully compiled your code, it would result in data corruption. So the compiler refuses, just in case.

Since in general the compiler can't really check if there is something mutable deep inside your type, it takes the safe route and rejects values (meaning "not functions") that are inferred to be generic.

---

Note that this applies to syntactic values, not logical ones. Even if your value is really a function, but isn't syntactically defined as such (i.e. lacks parameters), the value restriction still applies. As an illustration, consider this:

type T<'a> = { mutable x : 'a option }

let f t x = 
  t.x <- Some x

let g = f { x = None }

Here, even though g is really a function, the restriction works in exactly the same as with my first example above: every call to g tries to operate on the same generic value T<'a>

---

In some simpler cases the compiler can take a shortcut though. Thus, for example this line alone doesn't compile:

let f = List.map id

But these two lines do:

let f = List.map id
let x = f [1;2;3]

This is because the second line allows the compiler to infer that f : list int -> list int, so the generic parameter disappears, and everybody is happy.

In practice it turns out that this shortcut covers the vast majority of cases. The only time you really bump against the value restriction is when you try to export such generic value from the module.

---

In Haskell this whole situation doesn't happen, because Haskell doesn't admit mutation. Simple as that.

But then again, even though Haskell doesn't admit mutation, it kinda sorta does - via unsafePerformIO. And guess what - in that scenario you do risk bumping into the same problem. It's even mentioned in the documentation.

Except GHC doesn't refuse to compile it - after all, if you're using unsafePerformIO, you must know what you're doing. Right? :-)