2. List – Cons, Car, Cdr & Co

Lists are the most important data structures in functional programming languages. It is not for nothing that the first functional programming language, that is by the way the second oldest programming language (1958) is called LISP which stands for “LISt Processing languages”. LISP is all about working with lists to the point that even its source code is written with lists, so the border between data and code is blur, this strange property called homoconicity is really powerful! No more need for serialization, no need for remote procedure call systems, meta-programming is easy, creating new domain specific languages (DSL) becomes easy! To learn more about LISP (see my article about Macros).

What are the terms “cons”, “car” and “cdr”?

“cons” stands for “construct”, “car” for “Contents of the Address part of Register number” and “cdr” for “Contents of the Decrement part of Register number”. “car” and “cdr” were the names given to registers in the first LISP machines.  They are now the names of basic list operations available in LISP. “cons” is still in use in most functional languages to name this same operation.

These operators roles are:

• The cons function allocates a pair with two value references.
• The car function takes a pair and return its first value.
• The cdr function takes a pair and return its second value.

What is the relationship between these operations and lists?

If you think more carefully about it, I wrote that the cons operation makes pairs from two values. So what if you build a first pair holding in its first cell (the car cell) a value and in its second cell (the cdr cell) an other pair which contains as its first cell a value and as its second cell a pair and so on…

As the image above shows it, this would build a single linked list! However we need to know when the list ends. We could just say that if the last value is not a pair then it ends, but in this case it would be a somewhat non regular, and there would be a problem, how to represent an empty list? To solve this problem a special value exists, and surprisingly enough it is called “the empty list” ! So the image above represents a list of integers containing the values 42, 69, 613, the NIL at the end represents the empty list. If you read my article about recursion you may already have an idea about where this list definition is going to lead us.

Time to do it in F#!

In F# the cons operator is  (::), it is an infix operator . car and cdr are respectively head and tail from the List module, and finally the empty list is [].

You can use the F# interpreter fsi.exe in interactive mode to see the result of the command you type directly, you need to use ;; to end a command within the interpreter. In Visual Studio pressing Ctrl + Alt + F brings the F# Interactive Console.

You should notice that:

• After executing a command the result is displayed. In functional programming languages there is always a result. Everything is expression. To be functional code should avoid side effects. If there is no side effects and a function doesn’t return a value, we can assume that from the outside this function when called does nothing, since it cannot modify the environment (side effects), and it can’t return a result. Functional languages are classified by the notion of purity, which is how much they prevent programmers to use side effects. Haskell is for example a really pure language, F# allows imperative programming so it is less pure, but the way your code in F# can be pure. In non-pure functional programming languages a special value is used to represent the result of a function which does nothing else than side effects, in F# this value is the unit and is represented by  the () literal. 

• When the result is displayed val list indicates we were evaluating a value named “list”, the (:) operator specifies the type which is int list so a list of integer (this type could also have been written list<int>) , finally the value is indicated after the (=) operator. The list we built using  the cons operation is now written in the result  as [42; 69; 613], which the way you usually use to declare list literals in F#. So instead of using the cons operation in our sample we could have directly used the latter syntax.

• The car or the head of list is 42, and the cdr or tail is [69; 613] which is a list, since the list is made by pairs of pairs.

• List types are parameterized, the generic type is ‘a list (or list<’a> ) with ‘a being a type parameter. Type parameters are prefixed with a single quote. Thanks to this you can create different list types, for example int list, float list or string list.

What are the advantages of using single linked list?

Using the concept of pairs linked to each others for lists, makes them perfectly fit with the concept of recursion. Therefore you can easily create function working with lists in functional programming languages.

Look at this F# definition for function to compute the length of list for example:

If you remember the definition of fact in my previous article on recursion, you can describe this function as: length is a recursive function doing pattern matching on its first argument, if this first argument is the empty list then the result is 0, if it is a pair whose head is h and tail is t then add 1 to the length of the tail t (remaining of the list).

An other advantage of using pairs in functional programming is about side effects. If you want to make the list grows, you can just prepend a value to it. You use the cons operation with the element you want to add to the list as a first value, and the old list value as a second value for the pair, then without side effect you make the list grow. In the same way if you want to remove a value from a list, just drop the pair holding the concerned value, and its previous pair from the list and create a new pair with the previous pair value as first argument and the next pair as second argument to recreate the link.

How is this list related to the List class from System.Collections.Generic?

F# lists are not related to this class, since they are implemented using pairs whereas the List class from System.Collections.Generic uses a resizable array internally. To avoid the confusion a type alias ResizeArray has been created in F#. Accessing elements or appending elements in single linked list are not efficient operations since they have a complexity of O(n). In an array or array based list these operations are addressed in constant time. So in these cases you may consider to use ResizeArray or the F# arrays that I will introduce in my article on Sequences.

Comments

• Anonymous
  February 21, 2012
  The comment has been removed
• Anonymous
  April 26, 2012
  Did you put together a source code for this? Thanks.