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:
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:
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.