GIML: Lesson Two


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 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.


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.


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]