How to read F# type signatures?

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 retu开发者_运维技巧rns 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?

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.

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))

You could write a similar function in F# which has a type like you're proposing (but in F# it would be written as ('a * 'b -> 'a) * 'a * list<'b> -> 'a. However, the advantage of the existing function is that it's easy to partially apply it by only supplying a prefix of the arguments. For instance:

let sum = List.fold (+) 0

Using your definition, you'd have to write

let sum l = List.fold((fun (x,y) -> x + y), 0, l)

The reason for that is in Functional programming every function actually has only one parameter.

So lets say you have a function called Sum as :

int -> int -> int

It takes 2 int and return one int. Now if you call this function by just passing one int you won't get any compiler error, rather the return value will be of type int -> int. So you see this arrow notation fits with this behavior. This behavior is known as Currying. Check out : http://en.wikipedia.org/wiki/Currying