Does F# type inference works top-down (and left-right) only?

Question

I still cannot figure out why F# compiler cannot infer the type in the following example (taken from the Programming F# 3.0 book):

open System.IO

// type inference ok: fileInfos : string [] -> FileInfo []
let fileInfos (files : string[]) =
    Array.map (fun file -> new FileInfo(file)) files

// type inference does not work !?
let fileSizes (fileInfos : FileInfo []) =
    Array.map (fun info -> info.Length) fileInfos

The explanation in the book (page 62) is:

This is because type inference processes code from left-to-right and top-to-bottom, so it sees the lambda passed to Array.map before it sees the type of the array elements passed. (Therefore, the type of the lambda’s parameter is unknown.)

which is reasonable in this case (for fileInfos, type of file is inferred as string since the constructor FileInfo has its parameter as string; for fileSizes, there's no such information).

But I still have doubts because if the explanation is correct, then the type inference (a variant of Hindley–Milner's algorithm W) is so limited. Indeed, there's another source says:

... [F#] ... type inference works top-down, bottom-up, front-to-back, back-to-front, middle-out, anywhere there is type information, it will be used.

Edit: thanks to all for answers, I just add below some details to explain why I still get confused.

In the case of fileSizes, the compiler knows:

• filesInfo : FileInfo [],
• Array.map : ('a -> 'b) -> 'a [] -> 'b [],

it can replaces 'a by FileInfo, so there must be info : FileInfo in the lambda fun info -> info.Length

I can give an example where the type inference of F# shows that it's more capable than "left-to-right, top-to-bottom":

// type inference ok: justF : int [] -> (int -> int -> 'a) -> 'a []
let justF (nums : int []) f =
    Array.map (fun x -> f x x) nums

where the compiler infers correctly the type of f : int -> int -> 'a (obviously it cannot have such an inference if it looks only into the lambda).

Answer 1

F#'s type inference algorithm is somewhat limited around object instance member access - it doesn't attempt to work out the type "backwards" from them, so unless enough type information is already provided, it will just stop dead in its tracks.

This is not the case with record fields, for instance (note there's no annotation even on the function argument):

type FileInfoRecord = { length: int }

let fileSizes fileInfos =
    Array.map (fun info -> info.length) fileInfos

It's a conscious design trade-off, however - I remember hearing that it could be improved, but at the cost of less reliable intellisense and more confusing error messages (i.e. it would work fine for simple cases, but when it fails, it would fail further away from the actual line that caused the problem). With the current setup, the workaround is straightforward - just put an annotation on the lambda's argument.

I suppose that that's the price to pay for running a Hindley-Milner style type inference alongside object-oriented type hierarchies with polymorphism and overloading.

Answer 2

In order to use left to right type inference you can change fileSizes using the pipe operator |>. Since it already knows that fileInfos is an array of FileInfo it can deduce that info must be a FileInfo:

// type inference now is ok
let fileSizes (fileInfos : FileInfo []) =
    fileInfos |> Array.map (fun info -> info.Length) 

The other way it does not work because the lambda function appears before it knows what the second parameter to Array.map is going to be. The pipe operator, on the other hand, already establishes that whatever comes after the pipe needs to receive an array of FileInfo.

In the case of fileInfos, like you correctly stated, it knows that file must be a string because that is the only type that new FileInfo(...) accepts. Now, imagine you wanted to use one of the OO members of info like ToUpper(). That would bring back the same error, because there could be any number of types that can have a member named ToUpper that returns a string:

// same type inference error
let fileInfos (files : string[]) =
    Array.map (fun file -> new FileInfo(file.ToUpper())) files

again you can fix it by passing files first using the pipe:

let fileInfos (files : string[]) =
    files |> Array.map (fun file -> new FileInfo(file.ToUpper())) 

When using record types F# looks for a type that has a member with the same name and assumes that is the type. That may not work correctly when there is more than one possibility. In that case it will pick the latest one declared or opened.