List.reduce partial application with type annotation gives error FS0030

Question

let ones = List.map (fun _ -> 1)

Can't be generalized and gives the FS0030 value error.

This can be fixed (among other ways) with a type annotation:

let ones<'a> : 'a list -> int list = List.map (fun _ -> 1)

However in the case of:

let count = List.fold (fun t _ -> t + 1) 0

What type annotation will work, or, why doesn't adding the type annotation help the compiler?

let count : 'a list -> int = List.fold (fun t _ -> t + 1) 0

(I know about List.length, or that I can use count x = x |> List.fold.. etc, what I'm trying to understand is why type annotation works for the List.map example, but not List.reduce)

Answer 1

Short answer

This is the correct syntax:

let count<'a> : 'a list -> int = List.fold (fun t _ -> t + 1) 0

---

Explanation

It's not the type annotation that helps, it's the generic parameter.
This will compile (and even work, kind of):

let count<'a> = List.fold (fun t _ -> t + 1) 0

The error FS0030 is not about the compiler not being able to figure out the type. It's about you declaring a value (not a function) whose type works out to be generic. For reasons too complicated to describe here, such values are not allowed. Or, more precisely, they are allowed, but only if you have indicated that you know what you're doing by explicitly specifying the generic parameter.

Even with the generic argument, however, the actual inferred type of the value may turn out not what you expect. For example, if you paste the above example into an F# code editor and hover on count, you will discover that its type is obj list -> int.

Strange? Here's even stranger - add another line right after the definition:

let count<'a> = List.fold (fun t _ -> t + 1) 0
let c = count [1..5]

Now hover on count - its type became int list -> int.

Strange? Here's even more stranger :-)

let count<'a> = List.fold (fun t _ -> t + 1) 0
let c = count [1..5]
let c2 = count ["a"; "b"; "c"]

Now the third line doesn't compile at all, complaining that "a", "b" and "c" are expected to be int.

WTF?
This is a peculiarity of F# - inferring "provisional" most general type, and then fixing it based on actual usage. This is why in isolation count becomes obj list -> int (obj is the ultimate supertype), but as soon as you've used it with an int list, the compiler fixes the type to int list -> int instead. And if you try to use it with string list after that, it will understandably not compile.

One can observe same effect with polymorphic arithmetic operators:

let add x y = x + y
add 2.0 4.5
add "a" "b"

The first line in isolation infers to int -> int -> int, but as soon as you add the second line, the type of add becomes float -> float -> float (based on usage), and then the third line understandably fails.

This situation can be fixed by specifying the exact type you want:

let count<'a> : 'a list -> int = List.fold (fun t _ -> t + 1) 0

Now count will be a true generic function.

Answer 2

let count<'a> : 'a list -> int = List.fold (fun t _ -> t + 1) 0