ABSTRACT
Here we have a base case for an empty list:
INIL
and a recursion case:
icons of int * ilist
for an integer followed by another integer list. Note the recursive reference to ilist in the recursion case. The above example is:
– icons(1, icons(2, icons(3, INIL))); > icons(1, icons(2, icons(3, INIL))) : ilist
We can now write functions to process linked lists of integers. Once again, the structure of the datatype helps determine the structure of the function with a base case for a terminating link INIL and a recursion case for icons. For example, to find the sum of the elements of an integer list:
– (* sum ilist *) fun isum INIL=0 | isum (icons(v, l))=v+isum l;
> val isum = fn: ilist -> int
Thus:
– isum (icons(1, icons(2, icons(3, INIL)))); > 6 : int
because:
isum (icons(1, icons(2, icons(3, INIL)))) ==> 1+isum (icons(2, icons(3, INIL))) ==> 1+2+isum (icons(3, INIL)) ==> 1+2+3+isum INIL ==> 1+2+3+0 ==> 6
10.2 String linked lists
Suppose we now want to define linked lists of strings, for example:
We can use a similar datatype to that for integer lists:
– datatype slist = scons of string * slist | SNIL; > datatype slist = scons of string * slist | SNIL
con scons = fn: string * slist -> slist con SNIL = SNIL : slist
so the above example is:
– scons("ape", scons("bat", scons("cat", SNIL))); > scons("ape", scons("bat", scons("cat", SNIL))) : slist
Once again, we can write functions with a base case for the terminating link SNIL and a recursion case for scons. For example, to join all the elements of a string list together:
– (* implode slist *) fun implode SNIL = "" | implode (scons(s, l)) = s^implode l;
> val implode = fn : slist -> string
Thus:
– implode (scons("ape", scons("bat", scons"cat", SNIL)))); > "apebatcat" : string
because:
implode (scons("ape", scons("bat", scons("cat", SNIL)))) ==> "ape"^implode (scons("bat", scons("cat", SNIL))) ==> "ape"^"bat"^"implode (scons( "cat", SNIL) ) ==> "ape"^"bat"^"cat"^implode SNIL ==> "ape"^"bat"^"cat"^""==> "apebatcat"
10.3 Generalized lists
If we compare the datatypes for integer lists:
datatype ilist = icons of int * ilist | INIL
and string lists:
datatype slist = scons of string * slist | SNIL
we can see that they are essentially the same apart from the use of the types int and string. We can generalize to lists of any type by replacing the specific type with a type variable:
– datatype ′a list = cons of ′a * ′a list | NIL; > datatype ′a list = cons of ′a * ′a list | NIL
con cons = fn: ′a * ′a list -> ′a list con NIL = NIL : ′a list
Now, we can write the above examples as:
– cons(1, cons(2, cons(3, NIL))); > cons(1, cons(2, cons(3, NIL))) : int list – cons("ape", cons("bat", cons("cat", NIL))) ; > cons("ape", cons("bat", cons("cat", NIL))) : string list
Note that, in the first example, the system deduces that the whole structure is of type int list because the individual elements are of type int. Similarly, in the second example, the system deduces that the whole structure is a string list because the individual elements are string.
