Exercise #4

Functions as values

All functional languages allow functions to be used just like regular values. In fact, the notion of creating a function as a value "on the fly" is so common that SML provides an easy way to describe an anonymous function:

  val f = fn x => x * x;

This is quite reminiscent of

  fun f      x  = x * x;

but does not require us to bind the generated function to a name.

Determine whether functions written in the val style above can be recursive.
Implement a function mk_inc which takes an integer i and returns a function which, in turn, increments its arguments by i. Give the type of this function. How does this type relate to the type you would expect regular addition to have?
Standard ML provides a map function. Pass (mk_inc 5) to the map function and determine the type of the result you get. Next, determine what the map function really does based on what you gathered from the result (you may have to do further calls for this).
Implement a function filter which takes, as arguments, a list of integers and another function p mapping to bool, and returns a list containing all values in the original list for which p returns true.

Standard ML is installed at /tools/cs/smlnj/bin/sml on the CSEL machines.