Signature of higher order functions in SML

Question

I have been trying to understand Higher Order Functions in SML. I know how to write simple higher order functions and also understand the signature. One example is:

fun increment list = map (fn x=> x + 1) list;
val it = fn: int list -> int list

However, I cannot understand the signature of the following higher order function:

fun add  x y = x + y;
val add = fn: int -> int -> int

The function could be written as:

fun add (x,y) = x+y;
val add: fn : (int * int) -> int 

which I understand. But in the previous function, I fail to understand how the order of operations work. Does the function take two parameters at once, or does it take one at a time producing a new function which then produces the required result? How would it work for any other higher order function?

I need to build the concept about the signature of higher order functions for my homework as well as my exams coming up in a few weeks.

Answer 1

One thing to keep in mind is that all SML functions take exactly one argument. That argument may be a pair, as in your second add function, or an int, as in your first add function. You are correct that the first add returns a function of type int -> int. You could also have written

fun add1 x = fn y => x + y

which makes it more clear that it takes a single argument. Or even

val add1 = fn x => fn y => x + y

(FWIW, your double function looks a bit odd. It ignores its argument, and returns the same result every time.

fun increment list = map (fn x => x + 1) list

is probably what you meant.)

Answer 2

In SML, functions can be curried.

  - fun add x y = x + y
  val add = fn : int -> int -> int

is curried. This means that it can be partially applied, like this:

  - fun add2 x = add 2 x;
  val add2 = fn: int -> int
  - add2 3;
  val it = 5 : int

If we write the function as:

  - fun add2tuple(x,y) = x + y;
  val add2tuple = fn : (int * int) -> int

We are not actually passing in two parameters, but one tuple. That the tuple contains two integers is a description of the tuple's type.

• If we write the function in curried form, then the function parameters are not placed in a tuple.

• In the curried form, a function fun f p1 p2 ... pn = ... can be partially applied by passing between 1 and n-1 arguments.

But a function whose parameter is a single tuple cannot be partially applied.

- fun addordered x y = x + (2 * y);
val addordered = fn : int -> int -> int
- addordered 2 3;
val it = 8 : int
- fun addordered2 x = addordered x 2;
val addordered2 = fn : int -> int
- addordered2 3;
val it = 7 : int

This example might clarify that the tuple is a single thing:

- fun add3tuple(x,y,z) = x + y;
val add3tuple = fn : int * int * 'a -> int
- add3tuple(3,4,5);
val it = 7 : int
- add3tuple(3,4,"Hello World");
val it = 7 : int

Hope you enjoy Dan Grossman's class.