SML List Examples                            CSE 215 Fall 2007


Let us explore "lists".  A list is a finite sequence 
of elements, or a "container" for any number of elements.  
You can give a list explicitly, using square barckets,
with commas as separators:


Here is a list of integers:
- [1,2,3,4,5,6,7,8];
val it = [1,2,3,4,5,6,7,8] : int list

Lets name the above list "z" to use it later:
- val z=it;
val z = [1,2,3,4,5,6,7,8] : int list

- z;
val it = [1,2,3,4,5,6,7,8] : int list

The joining operator, to combine ("catenate" or "concatenate")
two lists into one larger list, is written "@":
- [1,2,3] @ [4,5,6];
val it = [1,2,3,4,5,6] : int list


Lets make a list with 16 elements.  Only the first 12 print out:
- z@z;
val it = [1,2,3,4,5,6,7,8,1,2,3,4,...] : int list

Execute this command (once) so in the future lists will print out
with up to 1000 elements:
- Compiler.Control.Print.printLength := 1000;
val it = () : unit

Now we see all 16 elements:
- z@z;
val it = [1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,8] : int list

The "@" operation for lists is like "^" for strings:
- "qwert" ^ "yuiop";
val it = "qwertyuiop" : string



All elements of a list must be the same type.
List elements can be real numbers:
- [1.2, 4.0, 0.01];
val it = [1.2,4.0,0.01] : real list

Here is a list of lists:
- [ [1,2], [], [1,2,3], z];
val it = [[1,2],[],[1,2,3],[1,2,3,4,5,6,7,8]] : int list list


The "head" of a list is its first element.  It is extracted with 
the built-in method "hd":
- hd(z);
val it = 1 : int


The "tail" of a list is the list of everything after the head.
It is extracted with the built-in method "tl":
- tl(z);
val it = [2,3,4,5,6,7,8] : int list

- tl([1,2]);
val it = [2] : int list

- tl([2]);
val it = [] : int list


The empty list contains zero elements. 
- [];
val it = [] : 'a list

It is also called "nil":
- nil;
val it = [] : 'a list


The empty list does not have a head or a tail.  Asking for them
will generate an error message:
- hd([]);
stdIn:48.1-48.7 Warning: type vars not generalized because of
   value restriction are instantiated to dummy types (X1,X2,...)

uncaught exception Empty
  raised at: boot/list.sml:36.38-36.43


- tl([]);
stdIn:49.1-49.7 Warning: type vars not generalized because of
   value restriction are instantiated to dummy types (X1,X2,...)

uncaught exception Empty
  raised at: boot/list.sml:37.38-37.43


Write a recursive method to find the length of a list.  The base 
case is that the empty list has length 0.  The general case is 
that we add one to the length of the tail, which is calculated 
in a recursive call to the len function we are defining:
- fun len(L) = if L=[] then 0 else 1+len(tl(L));
val len = fn : ''a list -> int

recall z is an 8-element list:
- z;
val it = [1,2,3,4,5,6,7,8] : int list

- len(z);
val it = 8 : int

The empty list has length zero:
- len([]);
val it = 0 : int

- len([1,2]);
val it = 2 : int


Given a list of integers, we compute the sum of its elements with a
recursive method.  Add the head to the sum of elements in the tail.
The base case is that we output 0 for an empty list, (the identity 
element for addition).
- fun sum(L) = if L=[] then 0 else hd(L)+sum(tl(L));
val sum = fn : int list -> int

- sum([1,2,3,10]);
val it = 16 : int

- sum([]);
val it = 0 : int

- sum(z);
val it = 36 : int



Now do the analogous thing to find the max of all elements in a list
of integers.  First we make a max operation for two integers:
- fun max(a,b) = if a>b then a else b;
val max = fn : int * int -> int

- max(3,4);
val it = 4 : int

- max(4,3);
val it = 4 : int


Now a recursive method, maxL(), to find the maximum element of a list.  
Just take the max of the head with the maxL of the tail.
The base case is that we want to output negative infinity for an empty
list, because this is the identity element for max, but we use -1 here:
- fun maxL(L) = if L=[] then ~1 else max(hd(L), maxL(tl(L)));
val maxL = fn : int list -> int
 
- maxL(z);
val it = 8 : int
 
- maxL([0]);
val it = 0 : int

- maxL([]);
val it = ~1 : int



The above took lists apart, but did not build lists.  We can build lists
using the "@" operation:
- [1] @ [2,3,4,5];
val it = [1,2,3,4,5] : int list


The "cons" operator (for "construct") combines an element and
a list to make a larger list.  The element becomes the head of
the resulting list.  The list which is given as the second argument
to cons becomes the tail of the new list.  The cons operator is 
written with two colons, as "::".
- 1 :: [2,3,4,5];
val it = [1,2,3,4,5] : int list


Note the element goes on the left and the list on the right.
The opposite would generate an error:
- [2,3]::1;
stdIn:129.1-129.9 Error: operator and operand don't agree [literal]
  operator domain: int list * int list list
  operand:         int list * int
  in expression:
    (2 :: 3 :: nil) :: 1


Lets write a recursive function to create a list with n zeros:
- fun zeros(n) = if n=0 then [] else 0::zeros(n-1);
val zeros = fn : int -> int list

- zeros(7);
val it = [0,0,0,0,0,0,0] : int list


Lets make a function to generate a "countdown to zero" list.
Simply cons n to the front of a smaller countdown list.
The base case is that for n=0 we return [0]: 
- fun down(n) = if n=0 then [0] else n::down(n-1);
val down = fn : int -> int list

- down(7);
val it = [7,6,5,4,3,2,1,0] : int list


Combining it with the sum() method from above, we can sum the
numbers from 1 to 10:
- sum(down(10));
val it = 55 : int

Here is the sum of the numbers from 1 to 100:
- sum(down(100));
val it = 5050 : int


If we want to count up instead, the n goes at the right, so we
use the catenation idea instead of consing, because cons only
adds an element to the left: 
- fun up(n) = if n=0 then [0] else up(n-1)@[n];
val up = fn : int -> int list

- up(20);
val it = [0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20] : int list


We can try our maxL() method on that list:
- maxL(up(20));
val it = 20 : int


Lets write a function to reverse a list.  (We did something analogous
last week, but with strings.)  The base case is easy; there is no problem 
reversing an empty list.  The general case is to combine the reverse of
the tail with the head.  we need to catenate, not cons, because the 
element goes at the end (and cons only builds at the front).  Catenation
requires two lists, so we put square brackets around the head element,
making it a one-element list:
- fun rev(L) = if L=[] then [] else rev(tl(L)) @ [hd(L)];
val rev = fn : ''a list -> ''a list


- rev(z);
val it = [8,7,6,5,4,3,2,1] : int list


- rev(rev(z));
val it = [1,2,3,4,5,6,7,8] : int list


With reverse(), we could write another version of up() using down():
- fun up2(n) = rev(down(n));
val up2 = fn : int -> int list

- up2(50);
val it =
  [0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,
   28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50]
  : int list

- up(50);
val it =
  [0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,
   28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50]
  : int list


Recall how we used map to compute the square of each element in a list:
- fun s(n) = n*n;
val s = fn : int -> int

- map s z;
val it = [1,4,9,16,25,36,49,64] : int list


Lets write our own function like map, which will make a list of the squares
of the elements of a given list.  Simply square the head of a list and cons 
that with squaring everything in the tail: 
- fun mapsq(L) = if L=[] then [] else s(hd(L)) :: mapsq(tl(L));
val mapsq = fn : int list -> int list

- mapsq(z);
val it = [1,4,9,16,25,36,49,64] : int list


Here is the same idea, but add 1 to ("increment") each element of a list:
- fun inc(L) = if L=[] then [] else hd(L)+1 :: inc(tl(L));
val inc = fn : int list -> int list

- inc (z);
val it = [2,3,4,5,6,7,8,9] : int list


Lets write a function to extract the nth element from a list,
(We assume it has at least n elements, so we don't check for errors.)
If you want the first element, easy, that is the head.  If you want 
an element after the first, it is the n-minus-first element of
the tail: 
- fun extract(n,L) = if n=0 then hd(L) else 
=                    extract(n-1, tl(L));
val extract = fn : int * 'a list -> 'a

- extract(0, [1,2,3]);
val it = 1 : int

- extract(3, ["a", "b", "c", "d"]);
val it = "d" : string


It will generate an error if n does not make sense for the list:
- extract(100,z);

uncaught exception Empty
  raised at: boot/list.sml:37.38-37.43


To convert n to binary, the rightmost bit is easy: it is n mod 2.  In a
recursive program, we can create everything left of the rightmost
bit by converting  half of n to binary, i.e., apply the function we are
writing to n div 2.  We then add a bit to the right by using @ (as above).  
Finally, the base case is that when n=0 we create a list [0]:
- fun bin(n) = if n=0 then [0] else
=              bin(n div 2) @ [n mod 2];
val bin = fn : int -> int list

- bin(13);
val it = [0,1,1,0,1] : int list

- bin(6);
val it = [0,1,1,0] : int list

- map bin z;
val it =
  [[0,1],[0,1,0],[0,1,1],[0,1,0,0],[0,1,0,1],[0,1,1,0],[0,1,1,1],[0,1,0,0,0]]
  : int list list


The base case [0] makes sense if we want 0 to appear as:
- bin(0);
val it = [0] : int list


But we may prefer to remove all leading zeros with this base case:
- fun bin(n) = if n=0 then [] else
= bin(n div 2) @ [n mod 2];
val bin = fn : int -> int list

- map bin z;
val it = [[1],[1,0],[1,1],[1,0,0],[1,0,1],[1,1,0],[1,1,1],[1,0,0,0]]
  : int list list

- bin(0);
val it = [] : int list