15

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?

4 Answers 4

16

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.

2
  • Clear explanation, thanks. After reading this I wonder how I didn't see it before... Commented Jun 24, 2011 at 21:35
  • I don't think this is the reason we use the arrow notation (in types). After all, in lambda calculus, we use "->" in the type syntax but "." in the term syntax. [It may, of course, be true that we use -> in terms in F# because we use -> in types and the . was already taken.]
    – petebu
    Commented Jun 24, 2011 at 21:43
7

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))
1
  • same as kvb, good explanation, thanks -unfortunately I can accept only one answer Commented Jun 24, 2011 at 21:36
5

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

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

1
  • nice example, perfect complement to the above answers! But schönfinkeling is so much a better name for it :-) Commented Jun 24, 2011 at 21:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.