A Gentle Introduction to ML

By Andrew Cumming, Computer Studies, Napier University, Edinburgh andrew@dcs.napier.ac.uk

This service is hosted by http://www.cs.stonybrook.edu, mirrored from http://www.cs.nmsu.edu/~rth/cs/cs471/sml.html.
The original is at http://www.dcs.napier.ac.uk/course-notes/sml/manual.html.
There are mirrors (now including Trans Atlantic).

Introductions: In which we argue for correct programs and ask the questions: "Why use formal methods?" and "Why use functional programming?". We answer some common questions about the language. A disclaimer is included.
Medium: In which we discus computer aided learning, advise on the use of this document, the location of supporting resources and some alternatives to it.
"Hello world": In which we introduce the reader to ML by means of Tutorial One concerning expressions and simple functions. We see our first Diversion: The Reconciliation Ball
Types: In which we encounter polymorphism , Bindings, Pattern Matching and Lists and embark upon Tutorial Two concerning Types and Function Composition. We are diverted by Diversion: Distorting Bitmaps
Yet more types: In which we infer types and Curry functions. We allow ourselves to be diverted by The Mandelbrot Set
Pattern Matching and Recursion: In which tenses are altered and factorials are evaluated; also encompassing Tutorial Three concerning Recursion on Integers
List Processing: In which we are re-acquainted with the list and struggle with Tutorial Four concerning Recursion with Lists
Yet more on functions: In which we permit Incompleteness, Overlapping Left Hand Sides, Conditions and Anonymous Functions we encounter Tutorial Five concerning More Recursion. We also attempt Diversion Three concerning Language Translation
Common Recursive Patterns: In which we map, reduce and zip a variety of functions and lists. Tutorial Six is presented. We avail ourselves of Diversion Four concerning the routing of the Capital's Buses.
Election Special in which we examine the voting of the British Public since 1983.
Creating Data Types: In which we follow Tutorial Seven concerning Queues
Various Programming Techniques: In which we Accumulate using Parameters, Mutually Recurse and we Nest our Definitions. This is followed by Tutorial Eight concerning Accumulating Parameters

Functional Programming in ML

This is aimed at students with some programming skills, but new to functional languages. It consists almost entirely of exercises and diversions, these are intended to be completed at a machine with at least some supervision. It is not intended to replace teaching. It will most likely be possible to copy text from the hyper text viewer (possibly Netscape or Mosaic) and paste it directly into a window in which ML is running thus saving at least some re-typing.

Learning

This document is an attempt to guide the student in learning rather than to present the syntax and theory in an ordered fashion. A considerable amount of time must be invested in learning a new language, with ML it's worth it.

"Hello world"

All of the following tutorial material has been developed for Standard ML. It has been used with New Jersey ML and Edinburgh ML but should work with any other version. The ML prompt is "-". Expressions typed in are immediately evaluated and usually displayed together with the resulting type. Expressions are terminated with ";" Using New Jersey ML the following dialogue might take place:

- "Hello world";

val it = "Hello world" : string

When used normally the ML accepts expressions and evaluates them. The result is printed to the screen together with the type of the result. The last result calculated may be referred to as it. In the example above the interpreter does not have to do any work to calculate the value of the expression entered - the expression is already in its simplest - or normal form. A more tricky example would be the expression 3+4 this is evaluated to the value 7.

- 3+4;

it = 7 : int

Notice that the expression to be evaluated is terminated by a semicolon. The interpreter allows expressions to go over more than one line. Where this happens the prompt changes to "=" for example:

- 4 + 4 +

= 4;

val it = 12 : int

Defining functions

A function may be defined using the keyword fun. Simple function definitions take the form:

fun < fun_name> < parameter> = < expression>;

For example

fun double x = 2*x;

fun inc x = x+1;

fun adda s = s ^ "a";

These functions may be entered as above. To execute a function simply give the function name followed by the actual argument. For example:

double 6;

inc 100;

adda "cub";

Tutorial One : Expressions & simple functions ML has a fairly standard set of mathematical and string functions which we will be using initially. Here are a few of them

+	integer or real addition

-	integer or real subtraction

*	integer or real multiplication

/	real division

div	integer division	e.g. 27 div 10 is 2

mod	remainder		e.g. 27 mod 10 is 7

^	string concatenation	e.g. "cub"^"a"

All of the above are infix. That is the operator appears between the two arguments. For a list of in-built functions goto Appendix A

Define and test the functions double and triple. double is given below:
```
fun double x = 2 * x;
```
This function may be tested by entering an expression to be evaluated. For example
```
double 3;
```
The function times4 may be defined by applying double twice. This is function composition.
```
fun times4 x = double(double x);
```
Use double and triple to define times9 and times6 in a similar way.
Functions with more than one input may be defined using "tuples". Define and test aveI and aveR given:
```
fun aveI(x,y) = (x+y) div 2;

fun aveR(x,y) = (x+y)/2.0;
```
Notice how ML works out the type of each function for itself. Try...
```
aveR(3.1 , 3.5);

aveI(31, 35);
```
Evaluate the expression "one"^"one" . Define the function duplicate such that
```
duplicate "go" evaluates to "gogo"
```
Also define quadricate, octicate and hexadecicate. Hints:

Reflection

The ML interpreter has a very clear, simple operation. The process of interpretation is just that of reduction. An expression is entered at the prompt and is reduced according to a simple set of rules. Example: Evaluate times6 5

times6 5	= triple(double 5)	from defn of times6

		= triple(2*5)		from defn of double

		= triple(10)		multiplication

		= 3*10			defn of triple

		= 30			multiplication

Some pre-defined functions are ord, chr, size, substring. The type or signature of each may be discovered by entering the name of the function alone:
```
ord : string -> int

chr : int -> string

size : string -> int

substring : string * int * int -> string
```
The functions ord and chr convert characters to ASCII values and vice versa. size returns the number of characters in the string and substring accepts a string, the start position and length of the substring, note that the first character of the string is number zero. Suppose we wish to create the function clip which removes the last character from its input.
```
clip "been" = "bee"               clip "raven" = "rave"
```
If s is the input string we need to return the substring starting at 0 of length, one less than the size of the input string
```
fun clip s = substring(s,0,size s - 1);
```
Define the following functions given by example here
```
middle "badge" = "d"             middle "eye" = "y"

dtrunc "trouser" = "rouse"       dtrunc "plucky" = "luck"

incFirst "bad" = "cad"           incFirst "shin" = "thin"

switch "overhang" = "hangover"   switch "selves" = "vessel"

dubmid "below" = "bellow"        dubmid "son" = "soon"
```
Answers to tutorial 1

You may wish to try the self assessment exercise now.

Now would be a good time to try Diversion: The Reconciliation Ball

Types

The basic types available are integer, real, string, boolean. From these we can construct objects using tuples, lists, functions and records, we can also create our own base types - more of this later. A tuple is a sequence of objects of mixed type. Some tuples:

(2,"Andrew")	: int * string

(true,3.5,"x")	: bool * real * string

((4,2),(7,3))	: (int * int) * (int * int)

While a tuple allows its components to be of mixed type and is of fixed length, a list must have identically typed components and may be of any length. Some lists:

[1,2,3]	: int list

["Andrew","Ben"]	: string list

[(2,3),(2,2),(9,1)]	: (int * int) list

[[],[1],[1,2]]	: int list list

Note that the objects [1,2] and [1,2,3] have the same type int list but the objects (1,2) and (1,2,3) are of different types, int*int and int*int*int respectively. It is important to notice the types of objects and be aware of the restrictions. While you are learning ML most of your mistakes are likely to get caught by the type checking mechanism.

Polymorphism

Polymorphism allows us to write generic functions - it means that the types need not be fixed. Consider the function length which returns the length of a list. This is a pre-defined function. Obviously it does not matter if we are finding the length of a list of integers or strings or anything. The type of this function is thus

length : 'a list -> int

the type variable 'a can stand for any ML type.

Bindings

A binding allows us to refer to an item as a symbolic name. Note that a label is not the same thing as a variable in a 3rd generation language. The key word to create a binding is val. The binding becomes part of the environment. During a typical ML session you will create bindings thus enriching the global environment and evaluate expressions. If you enter an expression without binding it the interpreter binds the resulting value to it.

- val a = 12;

val a = 12 : int

- 15 + a;

val it = 27 : int

Pattern Matching Unlike most other languages ML allows the left hand side of an assignment to be a structure. ML "looks into" the structure and makes the appropriate binding.

- val (d,e) = (2,"two");

val d = 2 : int

val e = "two" : string

- val [one,two,three] = [1,2,3];

std_in:0.0-0.0 Warning: binding not exhaustive

		one :: two :: three :: nil = ...

val one = 1 : int

val two = 2 : int

val three = 3 : int

Note that the second series of bindings does succeed despite the dire sounding warning - the meaning of the warning may become clear later.

Lists

The list is a phenomenally useful data structure. A list in ML is like a linked list in C or PASCAL but without the excruciating complexities of pointers. A list is a sequence of items of the same type. There are two list constructors, the empty list nil and the cons operator ::. The nil constructor is the list containing nothing, the :: operator takes an item on the left and a list on the right to give a list one longer than the original. Examples

nil			[]

1::nil			[1]

2::(1::nil)		[2,1]

3::(2::(1::nil))	[3,2,1]

In fact the cons operator is right associative and so the brackets are not required. We can write 3::2::1::nil for [3, 2, 1]. Notice how :: is always between an item and a list. The operator :: can be used to add a single item to the head of a list. The operator @ is used to append two lists together. It is a common mistake to confuse an item with a list containing a single item. For example to obtain the list starting with 4 followed by [5,6,7] we may write 4::[5,6,7] or [4]@[5,6,7] however 4@[5,6,7] or [4]::[5,6,7] both break the type rules.

::	: 'a * 'a list -> 'a list

nil	: 'a list

To put 4 at the back of the list [5,6,7] we might try [5,6,7]::4 however this breaks the type rules in both the first and the second parameter. We must use the expression [5,6,7]@[4] to get [5,6,7,4]

Tutorial two : Types

Consider the following bindings. Try to predict the result before executing them.

val x = "freddy";

val y = size x;

val z = size;

val h::t = [1,2,3]; (* Ignore the Warning, note the bindings *)

val (a,b) = (5,6);

val (c,d) = (2,("xx","yy"));

val (e,(f,g)) = (1,(2,3));

val (i,j)::k = [(1,2),(3,4)];

val (l,m,n) = ("xx",(1,2));

val (p, _ ) = (12, 10);

val (q, 10) = (12, 10);

val (r, 11) = (12, 10);

val [s,[u,v],w] = [[(1,2)],[(3,4),(5,6)],[]];

Predict the type of each of these objects. Check your answer by entering each followed by the semicolon.

("two", true, 2);

["two", true, 2];

((1,2),(3,4,5));

[[1,2],[3,4,5]];

[(2,2,[1])];

[[],[[]],[]];

Consider the type of each of the following functions

fun fone(x:int) = [x,x,x];

fun ftwo(x) = (x,x,x);

fun fthree(x,y) = [x ^ "b", y];

fun ffour(x,y,z) = (x+(size y),z);

Find out the type of each of the in-built functions explode, rev, hd and tl. Try each function on a list or a string as appropriate. Make a note of each of the following: The type of explode and the name of its inverse. The type of rev and its inverse. The type of hd and what it is an abbreviation for The type of tl and what it is an abbreviation for. Evaluate each of the following; try to predict the result.
```
hd(explode "south");

hd(tl(explode "north"));

hd(rev(explode "east"));

hd(tl(rev(explode "west")));
```
Optional Questions:
The function composition operator is o (say of). We can use it to create functions from functions.
```
val first = hd o explode;

val second = hd o tl o explode;
```
Create the functions third, fourth and last in a similar manner. You should find that these functions extract a single character from a string. Notice that in a chain of composed functions the last is applied first.
Use the functions first, second ... to create the following:
```
fun roll s = fourth s ^ first s ^ second s ^ third s; 

fun exch s = second s ^ first s ^ third s ^ fourth s;
```
Test these functions on some four character string such as "ache" and "vile". To save typing you may use the function map - however as this is a higher order function which we have not yet covered you must not attempt to understand how it works.
```
val words = ["ache", "vile", "amid", "evil", "ogre"];

map roll words;

map exch words;
```
The two permutations roll and exch can be used to generate any permutation of four characters. For example
```
val what = roll o roll o roll o exch o roll;
```
What's what "what"? Using only function composition on roll and exch define the functions which perform the following.
```
fb	"seat"	-> "eats"

fc	"silt"	-> "slit"

fd	"more" 	-> "rome"
```
Warning : do not apply fb to "ears"

Hints:

Why not try the second self assessment now.

Now would be a good time to tackle Diversion: Distorting Bitmaps

Type inference

One of the clever features of ML is that it can work out types in many cases. This is not always trivial. Consider the "reasoning" required to determine the type of a function such as

fun madeup(a,b,c) = b+size(c)::a;

c is of type string because the function size is applied to it, b must be an int because it is the input to + where the other input is an int, a must be a list of integers as it is right hand side parameter of the cons operator where the left is an integer. It is possible to over-ride the type inference mechanism, this may be desirable in the interests of software engineering or necessary where the mechanism cannot cope. Consider the seemingly simple definition of sum which adds its two inputs:

- fun sum(x,y) = x + y;

std_in:11.18 Error: overloaded variable cannot be resolved :+

This masterpiece of interface design is telling us that ML cannot work out if x and y are integers or real numbers. + is an overloaded operator, that is it means either add integers or add reals, these are different operations, the correct meaning cannot be deduced from the context. One solution would be to add zero, either integer or real

fun sum(x,y) = x + y + 0;

While this is effective it is scarcely elegant. We can specify the type of either or both parameters as follows

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

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

Functions as objects

We have already seen how functions may be treated as objects when composing functions. For example if the functions double and triple are defined we may create a function times6 as the composition of the double and triple.

fun double x = 2*x;

fun triple x = 3*x;

The following three definitions for times6 are equivalent

fun times6 x = triple(double x);

fun times6 x = (triple o double) x;

val times6 = triple o double;

In the first case we explicitly define times6 to be the result of triple when applied to the result of double x. In the second case we apply the composition of triple and double to the parameter x and in the third case we do away with the parameter x altogether. The function composition operator o has type

fn : ('a -> 'b) * ('c -> 'a) -> 'c -> 'b

It accepts two functions and returns a third. Notice the order of function application is "back to front". The expression f o g is the function f applied to the function g - i.e. g is applied first then f is applied to the result.

The function tea applies its input function to a specific value for example:

fun tea f = f 3;

Consider what happens when we apply tea to double, the effect is to evaluate double at 3.

tea double = double 3 = 6

The function twice applies a function twice

fun twice f = f o f;

The pre-defined function map applies a function over a list. The function inc is straight forward it is of type int -> int

fun inc x = x + 1;

Consider the results of the following calls, write down your answer before using ML to check.

triple(inc 1)

(triple o inc) 1

(double o inc o triple) 1

(triple o inc o double) 1

tea double

tea inc

tea (double o inc)

twice double 3

twice (twice inc) 3

(twice twice) inc 3

map double [1,2,3]

map (inc o double) [1,2,3]

map twice [inc,double]

map tea [inc, double]

map tea (map twice [inc, double])

Curry 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 two integers Using tuples

- 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 Diversion: Mandelbrot

Pattern Matching

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 match the first two equations - on reaching the last equation x is temporarily bound to "stretch" and the right hand side, x^"ed" becomes "stretch"^"ed" evaluated to "stretched". More on pattern matching later....

Recursion

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

0	1

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 resulting in

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.

Take care

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);

Using built in functions.

There are many useful in-built string and mathematical functions. In many versions of ML you can view these by opening the right structure. For example to see all the standard string functions enter:

open String;

If you are lucky ML will respond with:

val chr = fn : int -> string

exception Chr = Chr

val ordof = < primop> : string * int -> int

val print = fn : string -> unit

val size = fn : string -> int

val explode = fn : string -> string list

val ord = fn : string -> int

val implode = fn : string list -> string

exception Ord = Ord

val substring = fn : string * int * int -> string

exception Substring = Substring

val length = fn : string -> int

val <= = fn : string * string -> bool

val < = fn : string * string -> bool

val ^ = fn : string * string -> string

val >= = fn : string * string -> bool

val > = fn : string * string -> bool

Other useful structures include Integer, Real, Bool, IO, System. A word of warning. If you open a structure you will lose the overloaded functions. For example you can usually use length on strings or lists, following the open String; statement you can no longer apply length to a list.

Tutorial three: Recursion on integers

What do these recursive functions do?
You can enter each into ML and check the type of input required by each. Simply try evaluating each function on a few values.
```
fun t 0 = 0

|   t n = 2+t(n-1);
```
Now try evaulating t for the values 0, 1, 2, 3 and 100.
```
t 0;

t 1;

t 2;

t 3;

t 100;
```
Hints
```
fun d 0 = "de"

|   d n = "do"^d(n-1)^"da";

fun h 0 = 1

|   h n = h(n-1)+h(n-1);

fun m(a,0) = 0

|   m(a,b) = a+m(a,b-1);

fun f 0 = 0

|   f n = 1-f(n-1);

fun g 0 = 0

|   g n = g(n-1)+2*n-1;

fun l 0 = 0

|   l n = n mod 10 + l(n div 10);

fun j 0 = nil

|   j n = (n mod 2)::j(n div 2);
```
You should find that the call h 20; takes several seconds to evaluate while h 40; takes several weeks - why is this?
To save typing you might consider using map to evaluate the functions over a list of values for example:
```
map t [1,2,3,4,5,6];
```
Each of the following functions can be defined in a similar way. An example has been given in each case:
```
sumto 4		= 4+3+2+1+0	        = 10

listfrom 4	= 4::3::2::1::nil	= [4,3,2,1]

strcopy("ab",4)	="ab"^"ab"^"ab"^"ab"^""	= "abababab"

power(3,4)	= 3*3*3*3*1	        = 81

listcopy(7,4)	= 7::7::7::7::nil	= [7,7,7,7]

sumEvens 8	= 8+6+4+2+0	        = 20

listOdds 7	= 7::5::3::1::nil	= [7,5,3,1]

nat 2	        ="succ("^"succ("^ "zero"^")"^")"	

			                ="succ(succ(zero))"

listTo 4	= nil@[1]@[2]@[3]@[4]	= [1,2,3,4]
```
Example: sumto We require two equations for this function, the base equation, in this case a value for sumto 0; and a recursive equation, how to get sumto n given sumto(n-1)
```
fun	sumto 0 = ??

|	sumto n = ?? sumto(n-1);
```
Example listcopy Given two parameters we must choose which one to recurse on. For listcopy the second parameter givens the number of copies to be made - this is the one to recurse on. There must be a base case, the value of listcopy(x, 0) for any value x; and the recursive case, the value of listcopy(x, n) given listcopy(x, n-1)
```
fun	listcopy(x, 0) = ??

|	listcopy(x, n) = ?? listcopy(x,n-1)
```
Hints:

List processing and pattern matching Example : sum of a list Consider the function sum which adds all the elements of a list.

sum [2,3,1] = 2 + 3 + 1 = 6

There are two basic patterns for a list - that is there are two list constructors, :: and nil. The symbol :: is called cons, it has two components, nil is the empty list We can write equations for each of these constructors with completely general components. The empty list is easy - sum of all the elements in the empty list is zero.

	sum nil 		= 0

In the cons case we need to consider the value of sum(h::t). Where h is the head of the list - in this case an integer - and t is the tail of the list - i.e. the rest of the list. In constructing recursive functions we can assume that the function works for a case which is in some sense "simpler" than the original. This leap of faith becomes easier with practice. In this case we can assume that function sum works for t. We can use the value sum t on the right hand side of the definition.

	sum(h::t) = ??? sum(t);

We are looking for an expression which is equal to sum(h::t) and we may use sum t in that expression. Clearly the difference between sum(h::t) and sum(t) is h. That is, to get from sum(t) to sum(h::t) simply add h

fun	sum nil = 0

|	sum(h::t) = h + sum t;

Example : appending (joining) two lists The infix append function @ is already defined however we may derive its definition as follows The append operator joins two lists, for example

[1,2,3] @ [4,5,6] = [1,2,3,4,5,6]

The definition of an infix operator allows the left hand side to be written in infix. Given two parameters we have a choice when it comes to deciding how to recurse. If we choose to recurse on the second parameter the equations will be

fun	x @ nil    = ??

|	x @ (h::t) = ??;

It turns out that this does not lead to a useful definition - we need to recurse on the first parameter, giving

fun	   nil @ x = ??

|	(h::t) @ x = ??;

The first equation is easy, if we append nil to the front of x we just get x. The second equation is more difficult. The list h::t is to be put to the front of x. The result of this is h cons'ed onto the list made up of t and x. The resulting list will have h at the head followed by t joined onto x. We make use of the @ operator within its own definition.

fun	   nil @ x = x

|	(h::t) @ x = h::(t @ x);

Of course the @ operator is already defined. Note that the actual definition used is slightly different. Example: doublist Consider the function doublist which takes a list and doubles every element of it.

doublist [5,3,1] = [10,6,2]

Again we consider the two patterns nil and (h::t). The base case is nil

	doublist nil 	= nil

A common mistake is to think doublist nil is 0. Just by looking at the type we can see that this would be nonsense. The output from doublist must be a list, not an integer. In considering the cons case an example may help. Imagine the execution of a particular list say doublist [5,3,1]. We rewrite [5,3,1] as 5::[3,1] and consider the second equation.

	doublist(5::[3,1]) = ??? doublist [3,1]

Thanks to our faith in recursion we know that doublist[3,1] is in fact [6,2] and so we ask what do we do to [6,2] to get our required answer [10,6,2]. We answer "stick ten on the front".

	doublist(5::[3,1]) = 10::doublist [3,1]

Returning to the general case with h and t instead of 5 and [3,1]:

	doublist(h::t) = 2*h :: doublist t

Tutorial four: Recursion with lists

Define sum and doublist as shown. Test both functions on the list [5,3,1].

fun	sum nil 		= 0

|	sum(h::t) 		= h + sum t;

fun	doublist nil		= nil

|	doublist(h::t)		= 2*h :: doublist t;

Define and test the following functions. An example execution has been given for each case.
```
len [4, 2, 5, 1] 	= 4

triplist [4, 2, 5, 1] 	= [12, 6, 15, 3]

duplist [4, 2, 5, 1] 	= [4, 4, 2, 2, 5, 5, 1, 1]

prodlist [4, 2, 5, 1] 	= 40
```
Check the function prodlist. If you always get the result zero it is probably because you have the base case wrong. Consider how ML executes a simple case such as prodlist [1]. Consider also that just as the result of adding all the elements in an empty list is zero - the identity element for addition, so the result of multiplying all the elements of an empty list is one, the identity element for multiplication. If you still need convincing of this then remember that 5^3 is five to the power three - what you get from multiplying three fives. However 5^0 is one, the result of multiplying no fives.
Define the function vallist which turns character digits into integers. You will need to use the in-built function ord.
```
vallist ["4","2","5","1"] = [4,2,5,1]
```
Define the function rev which reverses the order of a list. Note the comments made about adding elements to lists earlier.
```
fun	rev nil   = nil

|	rev(h::t) = (rev t)@ ??;
```

Define the following functions.

space ["a","b","c"]         = ["a"," ","b"," ","c"," "] 

flatten [[1,2],[3],[4,5]]   = [1,2,3,4,5]

count_1's [4,3,1,6,1,1,2,1] = 4

timeslist 4 [4, 2, 5, 1]    = [16, 8, 20, 4]

last [4, 2, 5, 1]           = 1

member (3, [4, 2, 5, 1])    = false

member (5, [4, 2, 5, 1])    = true

Pattern matching and recursion When defining a function over a list we commonly use the two patterns

fun	lfun nil		= ...

|	lfun(h::t)	= ... lfun t ...;

However this need not always be the case. Consider the function last, which returns the last element of a list.

last [4,2,5,1] = 1

last ["sydney","beijeng","manchester"] = "manchester"

The two patterns do not apply in this case. Consider the value of last nil. What is the last element of the empty list? This is not a simple question like "what is the product of an empty list". The expression last nil has no sensible value and so we may leave it undefined. Instead of having the list of length zero as base case we start at the list of length one. This is the pattern [h], it matches any list containing exactly one item.

fun	last [h] 		= h

|	last(h::t)	= last t;

This function has two novel features.

Incompleteness

When we enter the function as above ML responds with a warning such as

std_in:217.1-218.23 Warning: match non exhaustive

	h :: nil => ...

	h :: t => ...

The function still works, however ML is warning us that the function has not been defined for all values, we have missed a pattern - namely nil. The expression last nil is well-formed (that is it obeys the type rules) however we have no definition for it. It is an incomplete or partial function as opposed to the complete or total functions that we have seen thus far. You will naturally want to know how ML does treat the expression last nil. The warning given is a mixed blessing. Under certain circumstances a partial function is very useful and there is no merit in making the function total. However if we manage to compile a program with no warnings and avoid all partial functions we are (almost) guaranteed no run-time errors. The exhaustive checking of input patterns can be non-trivial, in fact the algorithm which is used in non polynomial.

Overlapping left hand sides

As the pattern [h] is identical to the pattern h::nil we might rewrite the definition

fun	last(h::nil) = h

|	last(h::t)   = last t;

Examining the patterns of the left hand side of the = we note that there is an overlap. An expression such as 5::nil will match with both the first equation (binding h to 5) and the second equation (binding h to 5 and t to nil). Clearly it is the first line which we want and indeed ML will always attempt to match with patterns in the order that they appear. Note that this is not really a novel feature as all of our first examples with the patterns x and 0 had overlapping left hand sides.

Further examples

Define the following functions and test them. You may wish to use the given input to get an idea of what they do. Some of the functions are partial, some have overlapping left hand sides. Determine if they are not defined or are "over defined".

fun	hdify nil 		= nil

|	hdify((h::_)::t) 	= h::(hdify t);

fun	tlify nil               = nil

|	tlify((_::t)::t')	= t::(tlify t');

fun	trans (nil::_) 	        = nil

|	trans x 		= hdify x ::(trans(tlify x));



fun	altern(nil, nil) 	= nil

|	altern(h::t, h'::t')	= h::h'::altern(t,t');



fun	diff(nil,x)		= x

|	diff(x,nil)		= x

|	diff(_::t,_::t')	= diff(t,t');





hdify [[1,2,3],[4,5,6],[7,8,9]];

tlify [[1,2,3],[4,5,6],[7,8,9]];

trans [[1,2,3],[4,5,6],[7,8,9]];

altern([1,2,3],[4,5,6])

diff([1,2,3,4],[5,6])

diff([1,2],[3,4,5,6])

Conditions

Where possible we use pattern matching to deal with conditions, in some cases this is not possible. We return to the function to convert present to past tense. The general rule - that we append "ed" does not apply if the last letter of the verb is "e". We can examine the last character of the input by applying explode then rev then hd. The improved version of past should give

past "turn" = "turned"

past "insert" = inserted"

past "change" = "changed"

The special case irregular verbs are dealt with as before:

fun	past "run" = "ran"

|	past "swim" = "swam"

|	past x = if hd(rev(explode x))="e" then x^"d"

			else x^"ed";

Anonymous function

A function may be defined with being named. The syntax is as follows

fn < parameters> => < expression>

For example

- fn x => 2*x;

> it = fn : int -> int

- it 14;

> 28 : int

This can be particularly useful when using higher order functions like map

map (fn x=> 2*x) [2,3,4];

Tutorial five: More Recursive Functions

Type in and test the following functions, be sure that you understand what each does:

fun	index(0, h::t) 	= h

|	index(n, h::t) 	= index(n-1, t);

fun	takeN(0, h::t) 	= nil

|	takeN(n, h::t) 	= h :: takeN(n-1, t);

fun	dropN(0, x) 	= x

|	dropN(n, h::t)	= dropN(n-1,t);

Sorting. The insert function inserts an integer into an ordered list:
```
fun	insert (n:int) nil = [n]

|	insert n (h::t)    = if (n<h) then ...

				      else ...
```
Complete the definition and test insert. To sort a list we proceed recursively. Sorting the empty list is trivial, sorting a list (h::t) is a matter of inserting h into the sort t
```
fun	sort nil	= nil

|	sort (h::t)	= ...  
```
Define the function upto:
```
upto 5 8 = [5,6,7,8]
```
The following functions are required in the next diversion a) The function dropSpace returns a list with leading spaces removed. The function takeSpace returns just the leading spaces.
```
fun dropSpace nil   = nil

|   dropSpace(hh::t) = if hh=" " then dropSpace t else hh::t;

fun takeSpace nil   = nil

|   takeSpace (hh::t)= if hh=" " then hh::takeSpace(t)

					else nil;
```
Test these on exploded strings which start with spaces. Define the function dropNonSpace and takeNonSpace and use them to define firstWord and butFirstWord such that:
```
firstWord(explode "One fine day") = "One"

implode(butFirstWord(explode "One fine day")) = "fine day"
```

Diversion three: Language translation Write a program to translate English into Scots - for example

- scots("Do you know where Pat lives");

> "Do you ken where Pat bides"

Use the same functions to translate to politically correct speak

Help

You will need the function lex which turns a list of characters into a list of words. The functions firstWord and butFirstWord should help.

lex(explode "one fine day") = ["one", "fine", "day"]

A function to translate a single words is quite simple:

fun	franglais "house" 	= "maison"

|	franglais "dog" 	= "chien"

|	franglais "beware"	= "regarde"

|	franglais "at"		= "dans"

|	franglais "the"		= "le"

|	franglais x		= x;

The last line insures that if we have missed a word out it is unchanged:

franglais "table" = "table"

Given a words translator we now need to put back spaces and implode:

fun	addSpace s = s^" ";

A generalized translator then takes a "word function" f:

fun trans f = implode o(map (addSpace o f))o lex o explode;

Now try

trans franglais "beware the dog at Hectors house";

The function lex could be improved so that instead of searching for a space it searches for a non-alpha character. If we also partition the list rather than remove spaces the punctuation may be retained and spaces need not be reintroduced.

fun alpha s =  (s>="A" andalso s<="Z") orelse

			(s>="a" andalso s<="z");

fun takewhile f nil    = nil

|   takewhile f (h::t) = if f h then h::(takewhile f t) 

						 else nil;

fun dropwhile f nil    = nil

|   dropwhile f (h::t) = if f h then dropwhile f t else h::t; 

fun lex nil = nil

|   lex l = (takewhile alpha l)::

	    (takewhile (not o alpha) (dropwhile alpha l))::

	    (lex (dropwhile (not o alpha) (dropwhile alpha l)));

Common recursive patterns

You will have noticed that certain patterns crop up in recursive functions. The following functions double and increment every item in a list respectively:

fun	doublist nil = nil

|	doublist(h::t) = 2*h :: (doublist t);

fun	inclist nil = nil

|	inclist(h::t) = (h+1) :: (inclist t);

Plainly we can abstract out of this a function which applies a function over a list. This is map:

fun	map f nil = nil

|	map f (h::t) = (f h)::(map f t);

Alternative definitions for doublist and inclist are

val doublist = map (fn x=>2*x);

val inclist = map (fn x=> x+1);

Slightly more subtle is the connection between the functions sum and flatten (the function flatten turns a list of lists into a simple list)

fun	sum nil = 0

|	sum(h::t) = h + sum t;

fun	flatten nil = nil

|	flatten (h::t) = h @ flatten t;

This second pattern is the reduce pattern - we have a base value for the nil list, for a cons node we apply a binary (two input) function f which is applied to the head and the recursive call:

fun	reduce f b nil = b

|	reduce f b (h::t) = f(h,reduce f b t);

We can now redefine sum and flatten:

val sum = reduce (fn(a,b)=>a+b) 0;

val flatten = reduce (fn(a,b)=>a@b) nil;

In fact we can do even better, ML allows use to convert infix functions such as + and @ into the prefix form required using the keyword op.

reduce (op +) 0 [1,2,3,4];

reduce (op @) nil [[1,2],[3,4],[5,6,7]];

Tutorial six: some standard functions There are several standard, or at least common, list functions. Everyone uses map, it is a pre-defined function; reduce is pre-defined as fold in standard ML, however we will continue to our own reduce as the order of the arguments is different.

The following functions will be used in further work without comment.

fun	map f nil		= nil (* pre-defined anyhow *)

|	map f (h::t)		= (f h)::map f t;

fun	reduce f b nil		= b

|	reduce f b (h::t)	= f(h,reduce f b t);

fun	filter f nil		= nil

|	filter f (h::t)	= if f h then h::filter f t

				 else filter f t;

fun	member x nil 		= false

|	member x (h::t)	= x=h orelse member x t;

fun	zip f nil nil		= nil

|	zip f (h::t) (i::s)	= f(h,i)::zip f t s;

fun	fst(a,_)		= a;	(* Also try #1 *)

fun	snd(_,b)		= b;	(* Try #2 *)

Consider each of the following expressions:

map(fn s => s^"io") ["pat", "stud", "rat"];

map(fn i => [i]) [4, 2, 1];

map hd [[2, 3], [7, 3, 2], [8, 6, 7]];

map(hd o rev o explode)["final","omega","previous","persist"];

Define each of the following functions using map

ftrl([1, 7, 5, 3])=[3, 21, 15, 9]

fhel(["tom", "dot", "harriet"])=["t", "d", "h"]

fttl(["strange", "shout", "think"])=["range", "out", "ink"]

fsml(["war", "la", "tea", "per"])= ["swarm", "slam",...]

Determine what each of the following do

val r = reduce (fn(a,b)=>b@[a]) nil;

val p = reduce (op ::);

val dr = reduce (fn(a,b)=>a+10*b) 0;

fun m x = reduce (fn(a,b)=>(a=x) orelse b) false;

fun n x = reduce (fn(a,b)=>(a=x) andalso b) true;

val im = reduce (op ^) "";

val ts = reduce (fn(a,b)=>if a=" " then nil else a::b) nil;

Define each of the following using reduce

prodlist [4,2,5,1] = 40

flatten [[4,2,5],[],[1]] = [4,2,5,1]

count [3,2,5,1] = 4

duplist [4,2,5,1] = [4,4,2,2,5,5,1,1]

Determine what each of the following do

fun rm x = filter (fn a=> a

x);

val mx = reduce max ~1000000;

fun sq (x:int list) = zip (op * ) x x;

fun rprime x = filter (fn i => i mod x

0);

fun sieve nil   = nil

|   sieve(h::t) = h::sieve(rprime h t);

Suggested inputs to determine function behaviour:

p [1,2,3] [4,5,6]

dr [3,6,2]

m 3 [2,6,7]         m 3 [2,3,6,7]     m 3 [3,3,3,3]

n 3 [2,6,7]         n 3 [2,3,6,7]     n 3 [3,3,3,3]

ts(explode "One fine day")

im(ts(explode "One fine day"))

sieve(upto 2 500)

Diversion four: Where to change on the buses

We can represent a "bus route" by a pair, the "service number" and the "route list" which gives the places served by that bus route. Taking the number 4 bus as an example:

val routeList4 = ["Princes Street", "Haymarket",

				   "Craiglockhart"];

val busRoute4 = (4,routeList4);

We can represent some of Edinburgh's buses using the list stops, a more complete list may be found in /home/student/general/ml/buses :

val stops = [busRoute4,

(10,["Princes Street","Tollcross","Craiglockhart"]),

(23,["Trinity","Tollcross","Morningside"])];

Using this data we can construct the function numbersFrom, which gives a list of buses servicing a given location and placesTo giving a list of places served by a given bus.

Constructing numbersFrom:

We note that an expression such as (member "Haymarket") is a function which might be applied to a "route list" giving true if Haymarket is in the list.

member "Haymarket" routeList4

This evaluates to true. We can use a partially evaluated member function as the condition of a filter thus obtaining a list of "bus routes" required. As the available list is a list of "bus routes" rather than "route lists" we must apply snd before applying the condition

filter ((member "Tollcross")o snd) stops

Gives us just those members of stops for which Tollcross is in the route list. We wish to extract the "service number" from each of these. Hence

fun numbersFrom p = map fst (filter ((member p)o snd) stops);

Constructing placesTo:

We wish to filter only those "bus routes" with a matching number. To look for the 10:

filter ((fn x=>x=10) o fst)stops

We can now extract the second component giving a list of lists which we flatten:

fun placesTo n = flatten(map snd (filter((fn x=>x=n)o fst)

				stops))

Do it yourself

Construct functions which tell you which buses can get you from A to B without changing, or with one change. Prove or disprove the "Two bus conjecture" which states that you can get from anywhere to anywhere on two buses. More bus data available here.

Creating your own data types

As one would expect from a modern programming language it is possible to create new data types in ML. Having created the datatypes we can create functions using pattern matching just as with the in built type list.

Enumerated Types

Perhaps the simplest example is akin to the enumerated type in C or Pascal.

datatype direction = north | east | south | west;

Four constructors are created by this declaration they can be used as patterns in defining functions. For example right turns 90 it takes a direction and returns a new one.

fun	right north		= east

|	right east		= south

|	right south		= west

|	right west		= north;

As we might expect these functions can be treated as any other. For example

val	aboutface	= right o right;

val	left		= ...

Data types which carry data

We can construct data types which carry data - these are akin to variant record types in Pascal. Each variant consists of a constructor and various components. Example: the type money can be either cash or cheque.

datatype money	= cash of int | cheque of string * real;

The int associated with cash is the amount in pennies, a cheque carries the name of the bank and the amount in pounds. For example:

val guardian		= cash 45;

val flat		= cheque("Abbey National", 36500.00);

val busfare		= cash 50;

Pattern matching on such items may be used in defining functions:

fun	worth(cash x) = x

|	worth(cheque("BCCI",_)) = 0

|	worth(cheque("Baring",_)) = 0

|	worth(cheque(_,amount)) = floor(100.0*amount);

floor is a standard function to truncate and convert a real to an integer.

Polymorphism and syntactic sugar We can create a more general list by referring to 'a as a general type in place of the specific type int. We can also do away with the brackets by making the cons operator infix, the keyword infixr ensures that the association is to the right. In ML we use :: for cons.

infixr ::;

datatype 'a list = nil | :: of 'a * 'a list;

This gives use the normal definition of lists. Note that the [1,2,3] notation is an additional facility.

Example: Queues

We wish to represent a first-in first-out queue. The data structure is similar to lists in that there is a "empty" constructor similar to nil and an "add" constructor which corresponds to cons. The front of the queue is at the right, nearest the bus stop, items are added to the left. Consider the bus queue shown, boris is at the front of the queue, ivan is last.:

This will be represented as

"ivan" ++ "tanya" ++ "boris" ++ P

This object is a queue containing ivan added to tanya added to boris added to the empty queue.

"ivan" ++ ("tanya" ++ ("boris" ++ P))

The empty queue is P, chosen for its uncanny similarity to a bus stop, it indicates the position of the front of the queue. ++ is the add operator, it associates to the right like :: The ML code allowing such a declaration is as follows:

datatype 'a queue = P | ++ of 'a * 'a queue;

infixr ++;

The operations on a queue are front and remove. front returns the element at the front of the queue (without altering the queue), remove returns the rest of the queue with the first element removed. Note that both of these are strictly functions not procedures, remove does not change an existing queue it simply returns part of the queue, the original is still intact after the function call.

front() =

The function remove applied to the above queue returns the queue consisting of ivan and tanya:

remove() =

The following equations for front and remove may regarded as axiomatic - that is they serve as definitions of what a queue is, as well as providing a means of calculating expressions. We would normally start by considering the simplest patterns then move on to more complicated patterns. For example front P however in this case the front of an empty queue has no meaning, instead we consider the queue containing exactly one item as our simplest or base case. The queue containing one item has the pattern lonely++P where lonely is an item

front(lonely++P) = lonely

front( ++ ) =

A more general queue consists of one item at the back (muggins) added on to the rest of the queue (everyOneElse) this queue has the pattern muggins++everyOneElse. If everyOneElse is not empty then the front of the whole thing is the same as the front of just everyOneElse without muggins.

front(muggins++everyOneElse) = front everyOneElse

front( ++ ) = front()

Similarly removing one item from a queue gives the empty queue:

remove(lonely ++ P) = P

remove( ++ ) =

and remove(muggins ++ everyOneElse) has muggins as the last element together with what is left of everyOneElse when one item is removed, hence

remove(muggins++everyOneElse) = muggins++(remove everyOneElse)

remove( ++ ) = ++ remove()

This translates into ML with just a few keywords thrown in:

fun front(x++P) = x

|	front(x++q) = front q;



fun	remove(x++P) = P

|	remove(x++q) = x++(remove q);

When we enter this into ML we are kindly reminded that we have non-exhaustive patterns, that is both front and remove are only partial functions. Note that P is a specific queue (the empty one) whereas q stands for any queue and x stands for any item.

But what is the subtext?

Tutorial seven: queues Enter the queue definition as shown before:

infixr 5 ++;

datatype 'a queue = P | ++ of 'a * 'a queue;

fun	front(x++P) = x

|	front(x++q) = front q;

fun	remove(x++P) = P

|	remove(x++q) = x++(remove q);

Define the function unfair which takes two queues and returns a single queue with the first queue behind the second queue. An example call follows:
```
unfair("boris"++"tanya"++P,"ivan"++"olga"++P)

		= "boris"++"tanya"++"ivan"++"olga"++P
```
The definition is partially given
```
fun	unfair(P,r) = ...

|	unfair(x++q,r) = ...
```
At Armageddon the first shall be last and the last shall be first. Define the doomsday function which reverses the order of a queue.
```
fun	doomsday P =...

|	doomsday q  = ...
```
The function rude is used by ill mannered people to push to the front of a queue. Define the function rude based on the following:
```
fun	rude(pushy, P)    = ...

|	rude(pushy, x++q) = ...
```
Following a coup the first shall be last but the second in line shall be first, everyone else shuffles up one place. Define coup,
Define the function nthq which returns the first n items from a queue.
```
fun	nthq(q, 0) = ...

|	nthq(q, n) = ...
```
Write functions l2q to convert a list to a queue and q2l to convert a q to a list.
At road works, where two lanes of traffic converge, the two queues are combined fairly. That is cars from each lane alternate.
```
fair("Rolls"++"Jag"++"BMW"++P,"Lada"++"Robin"++"Mini"++P)

	= "Rolls"++"Lada"++"Jag"++"Robin"++"BMW"++"Mini"++P
```
Define the function fair - you will need to use pattern matching to deal with the cases where one of the queues is empty and the functions front, remove and unfair to deal with the general case.
```
fun	fair(q, P) = ...

|	fair(P, q) = ...

|	fair(q,q') = ...
```

Solutions

fun	unfair(P,r) = r

|	unfair(x++q,r) = x++unfair(q,r);

fun	doomsday(P) = P

|	doomsday(q) = front q ++ doomsday(remove q);

fun	rude(pushy,P) = pushy++P

|	rude(pushy,x++q) = x++rude(pushy,q);

fun	coup q = front q ++ remove q;

fun	nthq(q, 0) = P

|	nthq(q, n) = rude(front q, nthq(remove q,n-1));

fun	l2q nil = P

|	l2q(h::t) = h++l2q t;

fun	q2l P = nil

|	q2l(x++q) = x::q2l q;

fun	fair(q, P) = q

|	fair(P, q) = q

|	fair(q, q') = rude(front q',rude(front q,fair(remove q,remove q')));

Some useful programming techniques

Accumulating parameters

The examples of recursion we have seen so far are tail recursive. An accumulating parameter is another common form of recursive programming. As with the examples so far we usually have a base case - this returns the accumulating parameter. In the recursive case we perform some function to the accumulating parameter and pass it on. The accumulating parameter "builds up" its value during recursive calls, rather than while the recursion is "unwinding" as in the tail recursive case. An example is called for. To sum a list using an accumulating parameter:

fun suma(nil, acc) = acc

|   suma(h::t,acc) = suma(t,h+acc);

To find the sum we must supply the initial value for the accumulating parameter - in this case zero.

fun sum l = summa(l,0);

Consider the execution of an expression such as sum [2,5,3]

sum [2,5,3]= suma(2::5::3::nil, 0)

			(h is 2, t is 5::3::nil, acc is 0)

		= suma(5::3::nil,2+0)

			(h is 5, t is 3::nil, acc is 2)

		= suma(3::nil,5+2)

		= suma(nil,3+7)

		= 10

This technique should normally be shunned as it smacks of "efficiencyism" - the functionally correct programmer should at all times avoid discriminating on the grounds of execution efficiency. The best way to achieve this state of grace is to avoid consideration of execution at all, while it is relatively easy to suspend ones awareness of execution for a normally recursive function it is difficult to maintain the required aloofness when it comes to accumulating parameters, one finds oneself uncomfortably close to the machine oriented thinking of a C programmer.

Mutually recursive functions

These may be defined using "and"...

fun foo 0 = "toff"

|   foo n = bar(n-1)

and bar 0 = "berut"

|   bar n = foo(n-1);

Nested definitions

We can define values or functions within other expressions using the "let .. in .. end" structure. Items declared are naturally local.

fun sort nil = nil : int list

|   sort(h::t) = let

	fun insert(i,nil) = [i]

	|   insert(i,h::t) = if i>h then i::h::t else

				h::insert(i,t)

in insert(h, sort t) end;



fun rev l = let

	fun reva(nil,acc) = acc

	|   reva(h::t,acc) = reva(t,h::acc)

in reva(l,nil) end;



fun power(x,0) = 1

|   power(x,n) = let

	fun even n = (n mod 2) = 0

	val s = power(x, n div 2)

in if even x then s*s else x*s*s	end;

It may be useful to return two values from a function. The following returns both the minimum and the maximum in one "pass"

fun minmax [x] = (x, x)

|   minmax(h::t) = let

	val (mn, mx) = minmax t

in (min(h,mn),max(h,mx)) end;

Tutorial eight: accumulating parameters

Here are two common definitions for rev. The obvious definition:
```
fun revobv nil = nil

|   revobv(h::t)= (revobv t)@[h];
```
and the obscure definition
```
fun revobs l = let

	fun r(nil,acc) = acc

	|   r(h::t,acc)= r(t,h::acc)

in r(l,nil) end;
```
Try both definitions on some large lists (several thousand items) to determine which is most efficient.
The function countrep count consecutive repetitions of items and returns an item*int tuple list. e.g.
```
countrep ["a","a","b","c","c","c"] = 

				[("a",2),("b",1),("c",3)]
```
Use the function cr with accumulating parameters c (for the current character) and cn (current character count) to define countrep
```
fun cr c cn    nil = [(c,n)]

|   cr c cn (h::t) = if c=h then ... else (c,n):: ...
```
Averages. To calculate the mean of a list, sum the list and divide by the number of elements. To find the median take the middle element of the sorted list. For an even sized list take the mean of the middle two. The mode of a list is the most frequently occurring item. e.g.
```
mean   [1,3,3,5,6,6,6] = (1+3+3+5+6+6+6) div 7 = 4

median [1,3,3,5,6,6,6] = 5

mode   [1,3,3,5,6,6,6] = 6
```
Given that the list is in order, each of these may be calculated in one pass using accumulating parameters. Help with mean: We can accumulate the sum and the length of the list simultaneously, we simply divide these when we reach the end of the list
```
fun mean l = let

	fun sl(nil ,sum,len) = sum div len

	|   sl(h::t,sum,len) = sl(t,sum+...,len+...)

in sl(l,0,0) end;
```
For median we can recurs down the list at double speed throwing away two items at a time, the accumulating parameter starts at the whole list and discards every other item
```
fun median l = let

	fun med(nil,l) = hd l

	|   med(_::nil,l) = hd l

	|   med(_::_::t,_::t') = med(t,t')

in med(l,l) end;
```
this does not work correctly for even length lists - for such lists we do not wish to discard exactly half the list. For mode we must accumulate the current item and the number of repetitions and the most frequent so far and the number of occurrences.
```
fun mode(h::t)= let

	fun bestof (c,n) (c',n') = if n>n' then (c,n) else (c',n')

	fun cb(nil,curr,best) = bestof curr best

	|   cb(h::t,(c,n),best) = if h=c then cb(t,(c,n+1),best)

					else cb(t,(h,1),bestof(c,n)best)

in fst(cb(t,(h,1),(h,1))) end;
```

Trees

A binary tree consists of "leaves" and "nodes" (sometimes branches). The tree shown carries data at branches but not at the leaves. We can define such trees in ML with:

datatype tree =	leaf

|			node of int * tree * tree;

val egTree = node(4,node(2,leaf,leaf),node(5,leaf,

			node(8,node(7,leaf,leaf),node(9,leaf,leaf))));





                         4

                        / \

                       /   \

                      2     5

                     / \   / \

                              8

                             / \

                            /   \

                           7     9

                          / \   / \

This definition allows only integers to be carried as data at each node. Consider each of the following functions, give the value for each function for the example tree given.

fun	nNode leaf = 0

|	nNode(node(_,l,r)) = 1 + nNode l + nNode r;

fun	sum leaf = 0

|	sum(node(v,l,r)) = v + sum l + sum r;

fun	flip leaf = leaf

|	flip(node(v,l,r)) = node(v,flip r, flip l);

fun	depth leaf = 0

|	depth(node(_,l,r)) = 1+max(depth l, depth r);

Define each of the following functions

member : int * tree -> bool

member(5, egTree) = true

member(10,egTree) = false



double : tree -> tree

double(egTree) = node(8,node(4,leaf,leaf)...)



maxT : tree -> int

maxT egTree = 9



flatT : tree -> int list

flat egTree = [2,4,5,7,8,9]



insert : int * tree -> tree

insert(3, egTree) = 

node(4,node(2,leaf,node(3,leaf,leaf)), 

       node(5,leaf,node(8, node(7,leaf,leaf), 

                           node(9,leaf,leaf))))

Note that the insert function should return an ordered tree when given an ordered tree. An ordered tree is one in which all members of the left branch are less than or equal to the node value, and all members of the right branch are greater than or equal to the node value for every node in the tree.
In effect - when you flatten the tree it is in order. The example egTree is ordered.

Appendix A

open Integer

exception Abs = Abs

val makestring = fn : int -> string

exception Quot = Quot

exception Div = Div

val print = fn : int -> unit

exception Prod = Prod

exception Mod = Mod

exception Neg = Neg

exception Overflow = Overflow

exception Sum = Sum

val abs = fn : int -> int

val quot = <primop> : int * int -> int

val div = fn : int * int -> int

val * = <primop> : int * int -> int

val + = <primop> : int * int -> int

val mod = fn : int * int -> int

val min = fn : int * int -> int

val max = fn : int * int -> int

val - = <primop> : int * int -> int

val rem = fn : int * int -> int

exception Diff = Diff

val <= = <primop> : int * int -> bool

val < = <primop> : int * int -> bool

val ~ = <primop> : int -> int

val >= = <primop> : int * int -> bool

val > = <primop> : int * int -> bool



open String

val chr = fn : int -> string

exception Chr = Chr

val ordof = <primop> : string * int -> int

val print = fn : string -> unit

val size = fn : string -> int

val explode = fn : string -> string list

val ord = fn : string -> int

val implode = fn : string list -> string

exception Ord = Ord

val substring = fn : string * int * int -> string

exception Substring = Substring

val length = fn : string -> int

val <= = fn : string * string -> bool

val < = fn : string * string -> bool

val ^ = fn : string * string -> string

val >= = fn : string * string -> bool

val > = fn : string * string -> bool



open Real

val truncate = fn : real -> int

val makestring = fn : real -> string

val arctan = fn : real -> real

exception Div = Div

val print = fn : real -> unit

exception Exp = Exp

exception Sqrt = Sqrt

val real = <primop> : int -> real

val ceiling = fn : real -> int

exception Prod = Prod

exception Ln = Ln

exception Overflow = Overflow

val realfloor = fn : real -> real

exception Sum = Sum

exception Floor = Floor

val abs = <primop> : real -> real

val cos = fn : real -> real

val exp = fn : real -> real

val sqrt = fn : real -> real

val * = <primop> : real * real -> real

val + = <primop> : real * real -> real

val ln = fn : real -> real

val - = <primop> : real * real -> real

val / = <primop> : real * real -> real

val sin = fn : real -> real

val floor = fn : real -> int

exception Diff = Diff

val <= = <primop> : real * real -> bool

val < = <primop> : real * real -> bool

val ~ = <primop> : real -> real

val >= = <primop> : real * real -> bool

val > = <primop> : real * real -> bool



open IO

exception Io = Io

val std_in = - : instream

val std_out = - : outstream

val std_err = - : outstream

val open_in = fn : string -> instream

val open_out = fn : string -> outstream

val open_append = fn : string -> outstream

val open_string = fn : string -> instream

val close_in = fn : instream -> unit

val close_out = fn : outstream -> unit

val output = fn : outstream * string -> unit

val outputc = fn : outstream -> string -> unit

val input = fn : instream * int -> string

val inputc = fn : instream -> int -> string

val input_line = fn : instream -> string

val lookahead = fn : instream -> string

val end_of_stream = fn : instream -> bool

val can_input = fn : instream -> int

val flush_out = fn : outstream -> unit

val is_term_in = fn : instream -> bool

val is_term_out = fn : outstream -> bool

val set_term_in = fn : instream * bool -> unit

val set_term_out = fn : outstream * bool -> unit

val execute = fn : string * string list -> instream * outstream

val execute_in_env = fn

  : string * string list * string list -> instream * outstream

val exportML = fn : string -> bool

val exportFn = fn : string * (string list * string list -> unit) -> unit



open Bool

val not = fn : bool -> bool

val print = fn : bool -> unit

val makestring = fn : bool -> string

Appendix B Hints

Example branching

You can return to the section you just left by clicking on the button marked "back" on your viewer. This text is in a random position near the end of the document. You can also move about the document by moving the scroll bars (usually on the right). The main index is at the top of the document. You set a book mark or add positions to your "hot list".

Duplicate: the answer

fun duplicate s = s ^ s;

duplicate "go";

The label s is the formal parameter - given in the definition of duplicate. The value "go" is the actual parameter - given in an execution of duplicate. A common mistake is to put the formal parameter in quotes, perhaps in order to convince the interpreter that it really is a string. For example:

fun duplicate "s" = "s"^"s";

ML will accept this, however defines a function which is defined at exactly one value only. You can evaluate the expression duplicate "s"; only any other parameter value will fail. The expression duplicate "x"; for example will not evaluate, you will an error message such "uncaught Match exception"

Hints on Duplicate

We are to declare a function duplicate which accepts a string as input and returns the string concatenated with itself as output. If the input is some string s then output will be s^s

fun duplicate s = "You replace this string with the correct string expression";

Most browsers have a button marked "Back" which will take you from whence you came. You might like to try it now. Unless you want more hints

Hints on simple recursive functions

In creating recursive functions of this sort you must give two equations. The first is the base equation; for this we specify the value of the function at some fixed value of the parameter, often 0 or 1. The left hand side of the equation has the actual value 0 or 1 in place of the parameter, the right hand side of the = has the output required of the function at that value.
The recursive equation typically tells the system how to construct the n case from the n-1 case. On the left of the recursive equation we have n as the parameter, on the right hand side the function will appear within some expression however the call will be made to the function at n-1 rather than n.

fun sumto 0 = 0

|   sumto n = n + sumto(n-1);



fun listfrom 0 = []

|   listfrom n = n::listfrom(n-1);



fun strcopy(s, 0) = ""

|   strcopy(s, n) = s ^ strcopy(s,n-1);

Common mistakes include:

Getting the type of the base case wrong.
People often put 0 on the right hand side of the base case when they mean nil and vise versa. Think about the type of the output, if the result of the function should be a list then nil is commonly the base result. If the output is a number then the base case will be a number. Errors like this will be caught by the ML type checker - this gives difficult error messages however they may be of some help, typically it will say something like
```
  expected: int -> 'Z list

  found:    int -> int
```
This means that one of the equations implies that the output should be a list but other equation implies the output should be an integer.
People try to perform operations within the functions. Remember you can only describe the output on the right hand side you are not writing instructions for the machine to carry out as you would in a traditional language.
Missing parameters in the recursive call. If you are defining an function with two parameters then the function must have the parameters given explicitly wherever it appears, in all equations, on both the left and the right of the = sign.

Now go back and try the rest of the problems before getting the rest of the answers from here.

Computer Aided Learning

The user should have control at all times, you are not forced to go through the material in any particular order and you are expected to skip the dull bits and miss those exercises which are too easy for you. You decide. The author does not believe that CAL is a good way to learn. CAL is a cheap way to learn, the best way to learn is from an interactive, multi functional, intelligent, user friendly human being. The author does not understand how it is that we can no longer afford such luxuries as human teachers in a world that is teeming with under-employed talent. His main objection to CAL is that it brings us closer to "production line" learning. The production line is an invented concept, it was invented by capital in order to better exploit labour. The production line attempts to reduce each task in the manufacturing process to something so easy and mindless that anybody can do it, preferably anything. That way the value of the labour is reduced, the worker need not be trained and the capitalist can treat the worker as a replaceable component in larger machine. It also ensures that the workers job is dull and joyless, the worker cannot be good at his or her job because the job has been designed to be so boring that it is not possible to do it badly or well, it can merely be done quickly or slowly. Production line thinking has given us much, but nothing worth the cost. We have cheap washing machines which are programmed to self destruct after five years; cars, clothes, shoes - all of our mass produced items have built in limited life spans - this is not an incidental property of the production line, it is an inevitable consequence.

The introduction of CAL is the attempt by capital to control the educators. By allowing robots to teach we devalue the teacher and make him or her into a replaceable component of the education machine. I do not see how such a dehumanizing experience can be regarded as "efficient", the real lesson learned by students is that students are not worth speaking to, that it is a waste of resources to have a person with them. The student learns that the way to succeed is to sit quietly in front of a VDU and get on with it. The interaction is a complete sham - you may go down different paths, but only those paths that I have already thought of, you can only ask those questions which I have decided to answer. You may not challenge me while "interacting". I want students to contradict, to question, to object, to challenge, to revolt, to tear down the old and replace with the new.

Do not sit quietly and work though this material like a battery student. Work with other people, talk to them, help each other out.

Hints on Tutorial Two

You can simply enter these into ML. Note that the binding
```
val h::t = [1,2,3];
```
Leads to a warning on some systems, whereas the binding
```
val (l,m,n) = ("xx",(1,2));
```
results in an error, the types on the left and the right of the equals sign are incompatable.
In each case ML assumes the most general type possible. Note the difference between a tuple and a list.

fone : int -> int list

ftwo : 'a -> 'a * 'a * 'a

fthree : (string*string) -> string list

ffour : int * string * 'a -> int * 'a

"s" "o" "t" "s"

val third = hd o tl o tl o explode;

val fourth = hd o tl o tl o tl o explode;

val last = hd o rev o explode;

It is not always easy to work out the chain of functions for these permutations.

val fb = roll o roll o roll;

val fc = roll o exch o fb;

val fd = exch o fc o exch;

More hints on simple recursive functions

fun power(x,0) = 1

|   power(x,n) = x*power(x,n-1);



fun listcopy(x,0) = []

|   listcopy(x,n) = x::listcopy(x,n-1);



fun sumEvens 0 = 0

|   sumEvens n = n + sumEvens(n-2);



fun listOdds 1 = [1]

|   listOdds n = n::listOdds(n-2);



fun nat 0 = "zero"

|   nat n = "succ(" ^ nat(n-1) ^ ")";



fun listTo 0 = nil

|   listTo n = listTo(n-1) @ [n];

Comments

power:
The power calculation may be done in O(log n) time rather than O(n) time using a faster recursion

	fun square (n:int) = n * n;

	fun power(x,0) = 1

	|   power(x,n) = if n mod 2 = 0  (* is n even? *)

                    	then square(power(x, n div 2)) 

			else x*square(power(x, n div 2));

sumEvens:
We note that this is a partial function. If you attempt to run this with an odd input then it will loop forever...

	sumEvens 3 = 3::sumEvens(3-1)

		   = 3::sumEvens 1

		   = 3::1::sumEvens(1-1)

		   = 3::1::sumEvens(~1)

		   = 3::1::sumEvens(~1-1)

		   = 3::1::~1::sumEvens(~3)

		   ....

We allow partial functions. If you really feel the need to make your functions total then we can fix this:

	exception Whoops;

	fun sumEvens 0 = 0

        |   sumEvens n = if n>0 then n+sumEvens(n-2) else

				     raise Whoops;

listTo:
This is a clumsy definition. The "natural" way to add to a list is to the left, the list is essentially a stack and adding to the left is equivalent to a push operation. Adding to the right involves appending a (potentially) big list to a singleton list. This is expensive. It is a fairly common problem - getting your lists the wrong way round. It may be fixed by using an accumulating parameter or by using the standard function rev.
```
	val listTo = rev o listfrom;



	fun listTo n = let

		fun lt(0,acc) = acc

		|   lt(n,acc) = lt(n-1,n::acc)

		       in lt(n, nil) end;
```

The @ operator

The append operator is defined in the file "/usr/local/software/nj-sml-93/src/boot/perv.sml" and is given as:

  infixr 5 :: @

  fun op @(x,nil) = x

    | op @(x,l) =

    let fun f(nil,l) = l

          | f([a],l) = a::l

        | f([a,b],l) = a::b::l

        | f([a,b,c],l) = a::b::c::l

        | f(a::b::c::d::r,l) = a::b::c::d::f(r,l)

     in f(x,l)

    end

This version may be shown to be equivalent to the simpler:

  infixr 5 :: @

  fun nil   @ l = l

  |   (h::t)@ l = h::(t@l)

but it will run faster.

Disclaimer

Much of the material given here is my own personal opinion which you are encouraged to dispute. Please e-mail andrew@dcs.napier.ac.uk with comments, typos, spelling mistakes, contributions or complaints. I shall assume the right to edit and include any commentary in this document unless you specifically ask me not to. I shall add comments which answer specific points only and I will not attempt to ridicule your point of view - if it deserves nothing else then I will not include it. The best way to retain editorial control is to send the URL of your comments.

Anything but multi-mediocrity.

Comments & questions from students

Please send comments, questions or reviews to andrew@dcs.napier.ac.uk - this document gets several "hits" per day from around the world but no feedback. Let me know how you are using this (or why you are not). Let's hear from Texas.

James Sears stu09@central.napier.ac.uk, David Boyle stu77@central.napier.ac.uk, Craig Salter cs3ea3by@maccs.dcss.mcmaster.ca

Introduction

Towards Correct Programs

There has been a great deal of progress in recent years in defining methodologies and design techniques which allow programs to be constructed more reliably. Some would claim that object orientation for example builds on and improves on structured programming which undoubtedly contributes to a better process of software construction. Using a rational methodology software engineers can produce better code faster - this is to be applauded, however it does not bring us any closer to the goal of correct programs. A correct program is not just more reliable - it is reliable. It does not just rarely go wrong - it cannot go wrong. The correct program should be the philosophers stone for the programmer, the pole star of our efforts. Software engineering may allow the intellectual effort of the programmer to be used "more efficiently" however it does not necessarily give us accurate programs.

Away from testing

Testing is usually regarded as an important stage of the software development cycle. Testing will never be a substitute for reasoning. Testing may not be used as evidence of correctness for any but the most trivial of programs. Software engineers some times refer to "exhaustive" testing when in fact they mean "exhausting" testing. Tests are almost never exhaustive. Having lots of tests which give the right results may be reassuring but it can never be convincing. Rather than relying on testing we should be relying in reasoning. We should be relying on arguments which can convince the reader using logic.

The benefits and costs of correct programs

If correct programs were cheap and easy then we would all use them. In fact the intellectual effort involved in proving the correctness of even the simplest of programs is immense. However the potential benefits of a cast iron guarantee on a program would be attractive in many situations. Certainly in the field of "safety-critical" systems formal methods may have a role to play. It must however be admitted that the safety of many such systems cannot be ensured by software - no amount of mathematics is going to make a weapons system or a complex chemical plant safe. Formal methods may have a useful part to play in systems where there is a high cost of failure - examples such as power stations, air traffic control and military systems come to mind. The cost of failure in any of these cases may be in terms of human life. The really important market for such systems is in fact in financial systems where the cost of failure is money itself.

Why functional programming

Functional languages such as ML, Hope and Lisp allow us to develop programs which will submit logical analysis relatively easily. Using a functional language we can make assertions about programs and prove these assertions to be correct. It is possible to do the same for traditional, imperative programs - just much harder. It is also possible to write programs in ML which defy logic - just much harder. A functional language like ML offers all of the features that we have come to expect from a modern programming language. Objects may be packaged with details hidden. Input and output tend to be rather more primitive then we might expect, however there are packages which allow ML to interface with front ends such as X-windows.

Functional languages are particularly well suited to parallel processing - several research projects have demonstrated superior performance on parallel machines.

Summary

We compare Formal Methods and ML with some alternatives:

The development cycle: Traditional Software Development

Using informal language a specification may be open to interpretation. Using appropriate testing strategies we can improve confidence - but not in any measurable way. Mistakes/bugs are common and difficult to spot and correct.

The development cycle: Formal Methods

Using logic we can state the specification exactly. Using mathematics we may be able to prove useful properties of our programs. Mistakes/bugs are common and difficult to spot and correct.

The development language: Traditional Language

Using structured programming or object oriented techniques we can reuse code. Using structured programming or object orientation we can partition the problem into more manageable chunks.

The development language: ML

Using structured programming or object oriented techniques we can reuse code. We can partition the problem into easy to use chunks - plus there are often "higher-level" abstractions which can be made ML which would be difficult or impossible in a traditional language.

The run-time system: Traditional Language

The compiler can produce fast compact code taking a fixed amount of memory. Parallel processing is not possible (in general). Fancy GUI's may be added.

The run-time system: ML

Code is usually interpreted, the memory requirements are large and unpredicatable. parallel processing is possible Fancy GUI's may be added, with difficulty.

Some common objections to ML

If ML is so brilliant how come no-one uses it?: ML is widely used in the academic community, it has not been taken up by people in industry to any great extent. This may be because there are not enough people in industry who understand the language. The acceptance or rejection of a system or standard by industry is an extremly arbitrary process. There is no body or committee which decides which are good systems and which are bad, popular systems arise for all sorts of reasons. There have been cases when large corporations or cartels have effectively imposed standards on the rest of us. Sometimes these standards are good and contribute to secure stable environments in which good software practice may flourish - usually they don't because the commercial interests of the large corporations or cartels depend on us working with unstable systems that require upgrading every year or two. To summarise:; There is very little logic in the way that the fashions and the moods of industry develops. Industry flirts with structured programming or object orientation then is prepared to give up software engineering altogether because of the look and feel of Visual Basic.; The few people who may be capable of directing these fashions would run a mile from a free programming language which doesn't need changing.
ML is not a proper language 'cos it doesn't run on a PC.: It does actually. The point remains that it is a relatively expensive language to run - but then some versions of C++ are not any better. See the FAQ (comp.lang.ml.faq) for how to get hold of implementations.
ML is not a proper language 'cos it can't be used to build applications with 3D buttons and context sensitive help.: This is a serious issue. There is a system called eXene which allow ML to control X-Windows.; It should be conceded that tarting up a program is easier in Visual Basic than it is in ML, it maybe even easier in C or C++ than ML. As ML can read and write files it may be slotted into any other system, the fact that it has little in the way of HCI embedded protects it from fickle fashions. The windows and pull down menues applications that are being built today will quickly look as old fashioned as the character based forms of last year. With its text only interface ML has the advantage of looking old fashioned already. The chances are that if you write a program in ML today you will still be able to run it in ten years time. If you write it in C++ and use the Windows interface your chances of celebrating the program's tenth birthday are slim.
But it hasn't got a or a or even a .: Real programmers don't use buttons. If you seriously think you need to single step your programs there are tools available (using emacs for example), however the author believes that these are more trouble than they are worth.
Still not convinced.: Have you considered following another course? An MSc. in Object Oriented Software Engineering is offered by the Department of Computer Studies at Napier University; suitable for computing graduates, it is 100% ML free.

The functional language community

The functional language community is excessively dour. The functional ascetics forbid themselves facilities which less pious programmers regard as standard. When using functional languages we do away with notions such as variables and reassignments. This allows us to define programs which may be subjected to analysis much more easily. When a value is assigned it does not change during the execution of the program. There is no state corresponding to the global variables of a traditional language or the instances of objects in an object oriented language. When a definition is made it sticks. Reassignment does not take place. Getting used to this and finding alternatives the traditional structures such as loops which require reassignment is one of the hardest tasks for a programmer "converting" from a traditional language. The line

x := x+1;

may appear in a 3rd generation language and is understood to indicate that 'box' or 'location' referred to as 'x' has its contents incremented at this stage. We do not admit such concepts. 'x' is 'x' and 'x+1' is one more than x; the one may not be changed into the other. A program without a state is a simpler thing - it is easier to write the code and easier to reason about the code once written. It is harder to write poor code.

Functional languages are considered, by their devotees, to be higher level than third generation languages. Functional languages are regarded as declarative rather than imperative. Ordinary third generation languages such as Pascal, C (including flavours such as C++) and assembly instruct the computer on how to solve a problem. A declarative language is one which the programmer declares what the problem is; the execution of the program is a low level concern. This is an attitude shared with the logic language community (Prolog people).

Functional languages & teaching

Taken from the comp.lang.functional news group:

AT Oxford we've been teaching functional programming for a decade to our first year undergraduate students in Mathematics&Computation, and for the entire life (2 years) of the Computation Degree. The functional programming course is the very first course in Computation that our students attend.

Apart from in the first year (when we used ``T'' a language with much in common with Scheme) , we've used a statically-typed purely applicative, lazy functional language.

Our intentions in doing so include

1. our wish to remedy the view that computing's about twiddling with ``little structures'' (bits and bytes) with which undergraduates with previous computing experience are often infected when they arrive.

2. our wish to promote the idea that it is possible (even at an early stage, and with rather unsophisticated conceptual tools -- equational substitution) to prove formally some of the properties of programs. That is NOT to say that the only way of writing a program is to derive it in a functional language from a formal specification; simply to show that there huge areas of our science in which our intuitions can be supplemented by formal reasoning.

3. our wish to demonstrate that programs can be ``lawfully'' transformed in a way which keeps functionality invariant but improves efficiency.

4. our wish to demonstrate some of the ideas behind data abstraction.

It isn't our intention to try to foist the idea on our students that functional programming is the only way to build things, or that laziness is next to godliness.

On the whole we've found that even students who come to us with strong preconceptions about computing of the kind I described above, begin to appreciate these ideas quite quickly, and find themselves able to transfer at least some of them to their imperative programming practice. Many students find it rather easy to think more abstractly about d e s i g n questions after this course.

Bernard Sufrin

Medium

This document is in html - hyper text mark up language. html allows links to other resources on the internet however almost all of the links here are internal - that is they refer to other parts of the text. This document is basically linear however there are a few side branches (like this) which will take you to another part of the document. To return from such a branch use the back button on your browser.

How to use this document

It should be possible to copy text from the browser into another window. I usually work with three windows. The browser (such as Netscape) is the largest, another window has ML running and another has an editor. I typically will copy text from the browser into the editor where I will change it, then from the editor into the ML window to test it.

Do you need to do the Diversions?

The diversions are important - real learning takes place when the student is engaged in problem solving, using ML as a tool. The diversions are beginnings of projects, if you are asking the question "how can I do this" you will remember the answer much more successfully than if you are presented with a list of techniques. Check out Mindstorms: children computers and powerful ideas by Semour Papert. Having said this there is clearly no point in students slogging through diversions which hold no appeal for the individual.

Is this computer aided learning?

The intention is to produce a mildly interactive document, it should be compared to a text book rather than a CAL package.

Tutorial 3 question 1 : Hints

You should have obtained the following results:

t 0 = 0

t 1 = 2

t 2 = 4

t 3 = 6

t 100 = 200

You may even have postulated that the function t is the same as function double. It is, and here's why...

t 0 = 0	this is due to the first equation `fun t 0 = 0`
t 1 = 2 + t 0	this is because of the second equation `\| t n = 2 + t(n-1)` where n is 1. We know that `t 0 = 0` and so `2 + t 0` simplifies to `2+0` which is of course `2`
t 2 = 2 + t 1	again this comes from the second equation but this time with `2` in place of `n`. Now `t 1` is `2` and so `t 2` is `2+2`
t 3 = 2 + t 2	leads us to `tt 3` is `2 + 4`
t 100 = 2 + t 99	but `tt 99` is `2 + t 98`, in fact t 100 = 2 + t 99 = 2 + 2 + t 98 = 2 + 2 + 2 + t 97 = 2 + 2 + 2 + 2 + ... + 2 + t 0 Clearly the are 100 2's giving the value 200 added to `t 0` which is 0.

Back

Printing

Please do not print this document - it takes hours and uses upto 40 pages even using the smallest font. There are copies available in the library. If you really, really want to print it then set the font size to the smallest first. (Check under the Option Preferences menu). Put your copy in a binder or folder (I usually have spare binders) and give it to me to pass on to next year's students when you have finished with it.

Some answers to tutorial 1 questions

fun double x = 2*x;

fun triple x = 3*x;

fun times4 x = double(double x);

fun times6 x = double(triple x);

fun times9 x = triple(triple x);



fun duplicate s  = s^s;

fun quadricate s = duplicate(duplicate s);

fun octicate s   = duplicate(quadricate s);

fun hexadecicate s = quadricate(quadricate s);



fun middle s = substring(s, size s div 2,1);

fun dtrunc s = substring(s, 1, size  s -  2);

fun incFirst s = chr(ord s + 1) ^ substring(s, 1, size s -1);

fun switch s = substring(s,size s div 2,size s div 2) ^

	       substring(s, 0, size s div 2);

fun dubmid s  = substring(s,0,(1 + size s) div 2) ^

		substring(s,size s div 2,(1+size s) div 2);