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