Why does this confuse the F# compiler's type inference?

Question

No problem here:

module Seq =
    let private rnd = Random Environment.TickCount

    let random =
        fun (items : 'T seq) ->
            let count = Seq.length items
            items |> Seq.nth (rnd.Next count)

The signature of Seq.random is items:seq<'T> -> 'T. All good.

Yes, I know that I could just let random items = [...], that is not the point.

The point is that items is suddenly constrained to be type seq<obj> when I do this:

module Seq =
    let random =
        let rnd = Random Environment.TickCount
        fun (items : 'T seq) ->
            let count = Seq.length items
            items |> Seq.nth (rnd.Next count)

... i.e. I add the Random object as a closure. If I hover over random, Intellisense shows me that the signature has become items:seq<obj> -> obj.

Interestingly, if I select the code and hit [Alt]+[Enter] to execute it in F# Interactive, the signature shows as seq<'a> -> 'a. WTH??

So, what's going on, here? Why the confusion and inconsistency in type inference?

Answer 1

This is due to the so-called Value Restriction. Cutting a long story short, syntactical values cannot be generic, because it might break things when mutations occur, and the compiler cannot always reliably prove immutability. (note that, even though random is a function semantically, it is still a value syntactically, and that's what matters)

But sometimes the compiler can prove immutability. This is why your first example works: when the right side of a let is a straight up lambda expression, the compiler can tell with certainty that it is immutable, and so it lets this pass.

Another example would be let x = [] - here the compiler can see that the nil list [] is immutable. On the other hand, let x = List.append [] [] won't work, because the compiler can't prove immutability in that case.

This "relaxation" of value restriction is done in F# on a case-by-case basis. F# compiler only goes as far as to handle a few special cases: literals, lambda expressions, etc., but it doesn't have a full-fledged mechanism for proving immutability in general. This is why, once you step outside of those special cases, you're not allowed to have generic values.

You can technically defeat this by adding explicit type arguments. Logically, this tells the compiler "Yes, I know it's a generic value, and that's what I meant for it to be".

let random<'t> : seq<'t> -> 't =
    let rnd = Random Environment.TickCount
    fun items ->
        let count = Seq.length items
        items |> Seq.nth (rnd.Next count)

let x = random [1;2;3]

But this will still not do what you want, because behind the scenes, such definition will be compiled to a parameterless generic method, and every time you reference such "value", the method will be called and return you a new function - with a brand new rnd baked in for every call. In other words, the above code will be equivalent to this:

let random() =
    let rnd = Random Environment.TickCount
    fun items ->
        let count = Seq.length items
        items |> Seq.nth (rnd.Next count)

let x = random() [1;2;3]