How to read F# type signatures?

Question

I'm struggling with the F# type signature notation. For example let's say you have a Fold function:

let rec Fold combine acc l =
...

that may have this type signature:

('a -> 'b -> 'a) -> 'a -> list<'b> -> 'a

which I would read as

a function that has three arguments:

• a function that takes an 'a, a 'b and returns an a'
• an 'a
• a list of 'b

and returns an 'a.

But then it would make more sense for my cavemen brain to express it as

('a, 'b -> 'a), 'a, list<'b> -> 'a

I'm sure there is a semantic reason why parameters are separated with an arrow exactly the same way as the function return type, but somehow I'm missing it and didn't found a clear explanation in books/articles so far. Every time I see a type signature I have to stop quite a bit of time to understand it. I feel like I'm just missing that little piece of the puzzle that makes the "decryption" obvious.

Can someone please enlighten me?

Answer 1

I'm sure there is a semantic reason why parameters are separated with an arrow exactly the same way as the function return type, but somehow I'm missing it and didn't found a clear explanation in books/articles so far.

You're reading of the first function is correct. For instant deciphering, type signatures are expressed like this:

val functionName = inputType1 -> inputType2 -> ... -> inputTypeN -> returnType

Generally, arrow notation indicates a function is curry-able.

// val add4 : int -> int -> int -> int -> int
let add4 a b c d = a + b + c + d;;

// val f : (int -> int)
let f = add4 1 2 3 // returns (int -> int) waiting for last argument

Because the function is curried, you can technically write it like this:

// val add4 : int -> int -> int -> int -> int
let add4 = (fun a -> (fun b -> (fun c -> (fun d -> a + b + c + d))));;

// val f : (int -> int)
let f = fun x -> add4 1 2 3 x

If you think about it, the add4 signature is equivalent to this:

val add4 : int -> (int -> (int -> (int -> int) ) )

I believe we use arrow notation because it resembles the structure of the function when we explicitly curry arguments as shown above.

Answer 2

The signatures are written in that way because of what is called Currying. A slightly more accurate way of describing your function is that it takes a (function that takes a 'a and returns a function from a 'b to a 'a) and returns a function that takes a 'a and returns a function from a list<'b> to a 'a. Because of this the type signature can be rewritten as

('a -> 'b -> 'a) -> ('a -> (list<'b> -> 'a))