Exercise 3: Basic ML Programming

Functions with Many Arguments

You can also define functions in ML that (appear to) take more than one argument. The format for such a definition is as follows:

fun name var1 var2 ... = expression[var1, var2, ...];

For example, try typing in the following definition of the function add:

fun add x y = x + y;

You can think of this form of definition as a short hand for the following, longer, form.

val name = fn var1 => fn var2 => ...
    expression[var1, var2, ...];

The longer form of the definition makes it explicit that name is not, in fact, defined to be a function taking multiple arguments, but as a function that takes just one argument and returns another function as its result. For example, try evaluating add 5, then take the result (it) and apply it to 10. Use this feature to define a function inc in terms of add.

Recursive Functions

Functions may be defined recursively in ML. For example, consider the following definition of factorial:

fun factorial n =
    if n = 0 then 1 else n * (factorial (n - 1));

Define a recursive function of your own that takes an argument n and returns the nth Fibonacci number. (The Fibonacci numbers are: 1, 1, 2, 3, 5, 8, 13, 21, ... .)

Tuples

If x₁ is a value of type t₁, and x₂ is a value of type t₂, and so on up to x_n, then (x₁,x₂,... x_n) is a tuple value of type (t₁ × t₂ × ... t_n). In ML this type is written (t1 * t2 * ... tn). Try entering a few tuples in ML, for example: (1,2), (1,true,"hello"), and ((0,true),(1,false)). Be sure to examine the type ML assigns to each.

ML uses the notation #n t to select the nth element of the tuple t. Try it out, for example try #1(1,true,2).

Something like `#1' is not a true function in ML because ML does not know how to type it by its self. However, you can make such things into functions if you supply the typing information yourself. For example, the following definitions declare (in different ways) the functions ifst and isnd, which return the first and second elements respectively of a pair of integers.

val ifst = (#1:int * int -> int);

fun isnd (ip:int * int) = #2 ip;

Use these definitions to declare a function sum, which takes a pair of integers as its argument, and returns their sum.

Pattern Matching Tuples

ML lets you make bindings using pattern matching. For example, we can bind x and y to 1 and 2 simultaneously with the following definition:

val (x,y) = (1,2);

Pattern matching also works for binding values to function arguments. For example, we could have defined the function sum like this:

fun sum (x:int,y) = x + y;

Pattern matching also works with lambda-abstractions, so a third possible definition of sum is as follows:

val sum = fn (x:int,y) => x + y;

Currying

Recall the function add we defined early on in these exercises. What is the difference between add and sum?

Functions that take their arguments one at a time, like add, are said to be curried; while functions that take their arguments all at once as a tuple are said to be uncurried. These terms are named for the mathematician Haskell B. Curry, for whom the functional programming language Haskell is also named. It is easy to convert a curried function to its uncurried equivalent, and visa-versa.

Write a function curry that takes a function requiring its arguments as a pair, and converts it into its curried equivalent. Write a function uncurry that does the opposite.

Lists

Lists are another important data-structure in ML. ML lists must be of finite length, and all the elements of the list must be of the same type. If the elements of a list have the type t, then the list will have type t list. Here are two examples of lists: [] and [0,1,2,3]. What are the types of these expressions?

The basic tools for creating and manipulating lists are as follows:

Code	Type	Meaning
nil	'a list	the empty list
e::l	'a * 'a list -> 'a list	prepend e to l
null l	'a list -> bool	is l empty?
hd l	'a list -> 'a	the first element (the head) of the list
tl l	'a list -> 'a list	all but the first element (the tail) of the list

Use these tools to write the function append, which takes two lists and joins them together. Note that this function already exists in ML, except that it is an infix function called `@'

Constructors

The constants nil and :: are the constructors for lists. That is, they are the basic building blocks from which lists are made. For example, the syntax [1,2,3] is just a nice way of writing 1::2::3::nil. Inside ML lists are represented in this latter form.

When making a definition, we can pattern match against the constructors for any type, including lists, just as we did with pairs. For example, we can bind x to 1 and xs to [2,3] with the following definition:

- val (x::xs) = [1,2,3];
> val x = 1 : int
  val xs = [2, 3] : int list
- val (x::xs) = [1,2,3];

Pattern Matching With Clauses

It is possible to define a function as a collection of clauses, each associated with a different pattern. The various clauses are separated by the `|' symbol. When the function is applied to an argument, the fist clause that matches the argument is executed. (However, it is clearer - and therefore considered good practice - to avoid making definitions where two or more clauses could match the same value.) For example, the append function can be defined as follows:

fun append nil l = l
 |  append (x::xs) l = x::(append xs l)

Try writing a function in this form to reverse the elements of a list. (This function also exists already, it is called rev.) If the various clauses of your function definition cannot match every value to which it may be applied, you will be given a warning when you define the function.