GIML: Lesson Three
A function of more than one argument may be implemented as a function of a
tuple or a "curried" function. (After H B Curry). Consider the function to add
- fun add(x,y)= x+y : int;
val add = fn int * int -> int
The input to this function is an int*int pair.
The Curried version of
this function is defined without the brackets or comma:
- fun add x y = x+y : int;
val add = fn : int -> int -> int
The type of this function is int->(int->int).
It is a function which
takes an integer and returns a function from an integer to an integer. We
can give both arguments without using a tuple
- add 2 3;
it = 5 : int
Giving one argument results in a "partial evaluation" of the function.
For example applying the function add to the number 2 alone results in a
function which adds two to its input:
- add 2;
it = fn int-> int
- it 3;
it = 5 : int
Curried functions can be useful - particularly when supplying function
as parameters to other functions.
This would be a good time to consider the
Note for Moscow ML users
In the examples so far we have been able to define functions using a
single equation. If we need a function which responds to different input we
would use the if _ then _ else structure or a case statement in a traditional
language. We may use if then else in ML however pattern matching is preferred.
Example: To change a verb from present to past tense we usually add "ed" as a
suffix. The function past does this.
past "clean" = "cleaned" past "polish" = "polished"
There are irregular verbs which must be treated as special cases such
as run -> ran.
fun past "run" = "ran"
| past "swim" = "swam"
| past x = x ^ "ed";
When a function call is evaluated the system attempts to match the input
(the actual parameter) with each equation in turn. Thus the call past "swim"
is matched at the second attempt. The final equation has the free variable x
as the formal parameter - this will match with any string not caught by the
previous equations. In evaluating past "stretch" ML will fail to
first two equations - on reaching the last equation x
is temporarily bound
to "stretch" and the right hand side, x^"ed" becomes
In the following examples we use exactly two patterns for our functions.
The first pattern is the base case which is typically 0 or 1
the second is n which matches with all other numbers.
A typical function takes the form:
fun f(0) = ??||The equation used when the input is zero|
| f(n) = ??||The equation used when n is 1 or 2 or 3 ...
More on pattern matching later....
Using recursive functions we can achieve the sort of results which would
require loops in a traditional language. Recursive functions tend to be much
shorter and clearer.
A recursive function is one which calls itself either directly or indirectly.
Traditionally, the first recursive function considered is factorial.
n n! Calculated as
1 1*0! = 1*1 = 1
2 2*1! = 2*1 = 2
3 3*2! = 3*2 = 6
4 4*3! = 4*6 = 24
5 5*4! = 5*24 = 120
6 6*5! = 6*120 = 720
7 7*6! = 7*720 = 5040
12 12*11*10*..2*1 = 479001600
A mathematician might define factorial as follows
0! = 1
n! = n.(n-1)! for n>0
Using the prefix factorial in place of the postfix ! and using * for
multiplication we have
fun factorial 0 = 1
| factorial n = n * factorial(n-1);
This agrees with the definition and also serves as an implementation. To
see how this works consider the execution of factorial 3.
As 3 cannot be matched with 0 the second equation is used
and we bind n to 3
factorial 3 = 3 * factorial(3-1) = 3*factorial(2)
This generates a further call to factorial before the multiplication can
take place. In evaluating factorial 2
the second equation is used but this
time n is bound to 2.
factorial 2 = 2 * factorial(2-1) = 2*factorial(1)
Similarly this generates the call
factorial 1 = 1 * factorial 0
The expression factorial 0 is dealt
with by the first equation - it
returns the value 1. We can now "unwind" the recursion.
factorial 0 = 1
factorial 1 = 1 * factorial 0 = 1*1 = 1
factorial 2 = 2 * factorial 1 = 2*1 = 2
factorial 3 = 3 * factorial 2 = 3*2 = 6
Note that in practice execution of this function requires stack space
for each call and so in terms of memory use the execution of a recursive
program is less efficient than a corresponding iterative program. As
functional advocates we take a perverse pride in this.
It is very easy to write a non-terminating recursive function. Consider
what happens if we attempt to execute factorial ~1
(the tilde ~ is used as
unary minus). To stop a non terminating function press control C. Be warned
that some functions consume processing time and memory at a frightening rate.
Do not execute the function:
fun bad x = (bad x)^(bad x);