language design - Why is F#'s type inference so fickle?

Question

The F# compiler appears to perform type inference in a (fairly) strict top-to-bottom, left-to-right fashion. This means you must do things like put all definitions before their use, order of file compilation is significant, and you tend to need to rearrange stuff (via |> or what have you) to avoid having explicit type annotations.

How hard is it to make this more flexible, and is that planned for a future version of F#? Obviously it can be done, since Haskell (for example) has no such limitations with equally powerful inference. Is there anything inherently different about the design or ideology of F# that is causing this?

Answer 1

Is there anything inherently different about the design or ideology of F# that is causing this?

Yes. F# uses nominal rather than structural typing because it is simpler and, therefore, easier for mere mortals to use.

Consider this F# example:

let lengths (xss: _ [] []) = Array.map (fun xs -> xs.Length) xss

let lengths (xss: _ [] []) = xss |> Array.map (fun xs -> xs.Length)

The former does not compile because the type of xs inside the anonymous function cannot be inferred because F# cannot express the type "some class with a Length member".

In contrast, OCaml can express the direct equivalent:

let lengths xss = Array.map (fun xs -> xs#length) xss

because OCaml can express that type (it is written <length: 'a ..>). Note that this requires more powerful type inference than either F# or Haskell currently have, e.g. OCaml can infer sum types.

However, this feature is known to be a usability issue. For example, if you screw up elsewhere in the code then the compiler has not yet inferred that the type of xs was supposed to be an array so any error message it can give can only provide information like "some type with a Length member" and not "an array". With only slightly more complicated code, this quickly gets out of control as you have massive types with many structurally inferred members that don't quite unify, leading to incomprehensible (C++/STL-like) error messages.