Learning About Lists in OCaml

In Chapter 4 of OCaml from the very beginning, I learned about lists:

• A list is a collection of elements of the same type.  The type of the list is

(the type of the element(s)) list

E.g., a list of integers has the type int list.

• To define a list, put the elements in a pair of square brackets, and separate each element by a semicolon.  E.g.

[ 1 ; 2 ; 3 ; 3 ] is a list with element 1,2,3,3. I made a typo while doing the end of chapter exercise and learnt that

[1,2,3,3] is a list with a single element of type tuple!  A tuple is not a list.  So the operator for lists won’t apply to it.  From this website, I learnt that a tuple can contain elements of different types, so for example (3, “hello”,’x’) has type int*string*char.

• The empty list [] should be distinguished from the list of one element which contains the empty list [[]].
• The sequence of the elements in the list matters.
• The first element of the list is the head.  The rest is the tail.  Clearly, the tail is of the same type as the list it came from.
• A list with one element has the element as the head and an empty list as the tail.
• A list that is empty doesn’t have a head nor a tail.  Why can’t the empty list be the head or the tail of an empty list?  Looking into it further, I found that for the head, it’s because it should have the type the same as the element.  But the empty list is not of that type, which may cause problems.  For the tail, there may be problems if the tail has the same number of elements as the list it came from,
• OCaml defines two operators for list:
  • :: (cons) adds a single element to the front of a list.  It’s run time is constant.
  • @ (append) combines two lists into one.  It’s run time is dependent on the length of the list.
• Each Greek letter stands for any type in OCaml.  (This wasn’t very clear to me.  I hope we’ll return to this later.  Edit: See the ‘Inferring Generic Types’ section of this post.)
  • If two types are represented by the same Greek letter, then they must have the same type.
  • If two types are represented by different Greek letters, then they may or may not have the same type, and these functions are called polymorphic functions.

More on pattern matching

The author did not formally explain that when you pattern match, you can match your expression to a pattern and at the same time name them. E.g.

let rec sum l =
  match l with
    [] -> 0
  | h :: t -> h + sum t ;;

When l does not match the first pattern, i.e, when l is non-empty, h and t are named as though l is obtained from the expression h :: t.  Therefore, h is the first element of l, and t is the list that contains the tail of l.

Tail recursive functions

Recursive functions which do not build up a growing intermediate expressions are called tail recursive.  They are preferred because they have constant run time which does not depend on the length of the list.  One way to write tail recursive functions is to use an accumulating argument in an auxiliary function.  E.g. count_true_inner is the auxiliary function to convert count_true to be tail recursive:

let rec count_true_inner n l =
  match l with
    [] -> n
    | true::t -> count_true_inner (n + 1) t
    | false::t -> count_true_inner n t ;;

let count_true l =
  count_true_inner 0 l ;;

count_true_inner‘s first argument is the accumulating argument that counts the number of elements that are true.

Note: On p.142, answers to questions of the book, there is a typo:

The last character of the last line of the rev_inner function should be t, not l.  The program does not terminate otherwise because the list it recurses on does not get smaller.