Lists and the associated functions are commonly used data structures in ML. List processing programs contain the following basic elements in ML programming.

• •

  Recursively defined data.

• •

  Pattern matching.

• •

  Polymorphic functions

Let us lean these elements through list programming.

A list is a sequence of elements. In ML, a list of 1,2,3 is written as follows.

# [1,2,3];
val it = [1, 2, 3] : int list

This notation is a shorthand for the following expression.

# 1 :: 2 :: 3 :: nil;
val it = [1, 2, 3] : int list

:: is a right-associative binary operator for constructing a list. So 1::2::3::nil is interpreted as 1::(2::(3::nil)). $e$ :: $L$ is the list obtained by pre-pending the element e to the list L. nil is the empty list. int list is the list type whose component is type int.