Why F# fails to infer types as C# would do

Question

From the book by Tomas Petricek the following code doesn't work as compiler is unable to infer the type of the dt parameter:

> Option.map (fun dt -> dt.Year) (Some(DateTime.Now));;
error FS0072: Lookup on object of indeterminate type.

And if we specify type explicitly everything works fine:

> Option.map (fun (dt:DateTime) -> dt.Year) (Some(DateTime.Now));;
val it : int option = Some(2008)

Or we can use pipelining operator to "help" compiler to infer type:

> Some(DateTime.Now) |> Option.map (fun dt -> dt.Year);;
val it : int option = Some(2008)

The question is why F# compiler can't infer the type of the dt parameter? In this particular case it looks quite easy to infer the dt's type.

The logic behind it can be the following:

1. the signature of Option.map is map : ('T -> 'U) -> 'T option -> 'U option
2. the type of the last parameter is DateTime option
3. so our map usage looks like map : ('T -> 'U) -> 'DateTime option -> 'U option
4. the compiler then can try to substitute DateTime as 'T to see if it would be correct, so we have (DateTime -> 'U) -> 'DateTime option -> 'U option
5. then it can infer the 'U type by looking at the body of the lambda-function, so the 'U becomes int
6. and we finally have (DateTime -> int) -> 'DateTime option -> 'int option

So why F# can't do this inference? Tomas mentions in his book that F# infers types by going from the first to the last argument and that's why the order of arguments matters. And that's why F# can't infer the types in the first example. But why F# can't behave like C#, i.e. try to infer types incrementally starting with what is known?

In most cases F# is much more powerful when speaking about type inference... that't why I'm confused a bit.

Answer 1

So why F# can't do this inference?

F# could do that as OCaml does that. The disadvantage of this kind of more sophisticated inference is the obfuscation of error messages. OCaml taught us that the result generated such incomprehensible errors that, in practice, you always resort to annotating types in order to prevent the compiler from being led down a type inference garden path. Consequently, there was little motivation to implement this in F# because OCaml had already shown that it is not very pragmatic.

For example, if you do that in OCaml but mis-spell the method name then you will get a huge error message at some later point in the code where two inferred class types mismatch and you will have to hunt through it to find the discrepancy and then search back through your code to find the actual location of the error.

IMO, Haskell's type classes also suffer from an equivalent practical problem.

Answer 2

F# can do everything C#'s type inference can do...and much, much more. AFAIK, the extent of C#'s type inference is auto-typing a variable based on the right-hand side of an assignment.

var x = new Dictionary<string, int>();

The equivalent F# would be:

let x = Dictionary()

or

let x = Dictionary<_,_>()

or

let x = Dictionary<string,_>()

or

let x = Dictionary<string,int>()

You can provide as much or as little type information as you want, but you would almost never declare the type of x. So, even in this simple case, F#'s type inference is obviously much more powerful. Hindley-Milner type inference types entire programs, unifying all the expressions involved. As far as I can tell, C# type inference is limited to a single expression, assignment at that.