Cons lists in C++

Lisp and other functional languages have purely-functional lists; that is, lists that cannot be changed; this leads to a very different style of programming, and can save memory and time, since parts of the list can be shared among several lists; with the new std::shared_ptr in C++, implementing such a list is relatively simple.

Although lisp lists allow mixing of types (and so are equivalent to binary trees), we will implement typed lists, which allow elements of only one type, using templates. We want to provide 4 functions:

• cons, which takes an element and a list, and produces another list, containing that element as its first element (and the passed list as the elements after the first element; notice we're going to share this passed list).
• car, which takes a list and returns its first element (sometimes called head).
• cdr, which takes a list and returns another list, the list minus the first element (sometimes called tail).
• isEmpty, which returns true if the list is empty, false otherwise.

Since cons is the operation that makes the list, I am calling my node ConsNode and my list class ConsList (btw, boost has a somewhat similar structure, using template metaprogramming, which means it can only be defined at compile time; see bost::const). Our Node class can be defined as:
And we can define our list class, simply as a synonym for shared_ptr (notice that both shared_ptr and template typedefs are c++11 features; template typedefs are implemented in g++4.7 and newer). The shared_ptr is a smart pointer, that basically implements a reference-counter pointer; several shared_ptrs can point to the same dynamically allocated chunk of memory; every time one is destroyed (because it goes out of scope), the counter is decremented; when the counter reaches 0, the memory is deallocated by calling delete. This allows us to not worry about calling delete manually.
Now, cons is the function that will create a new list, given an old list and a new element (notice this does NOT change the original list at all; we want to avoid modifying the lists, so they can be shared as parts of other lists). Our cons function is going to call std::make_shared, which creates a new reference-counted chunk of memory (you can create a shared_ptr from a plain dynamically allocated pointer, but at the cost of an extra call to new). Our cons function looks like: And car, cdr and isEmpty are simply defined as: For convenience, we can define an operator<< ; notice we're using car, cdr and isEmpty, and using recursion. With car, cdr and isEmpty, we can define functions recursively, like we usually would do in lisp or scheme (well, with slightly ugly template syntax :). Below are examples for len (which returns the length of a list) and sum (which adds up all the elements of a list of numbers). And we could use lists in a main function, like below (notice how the lists share a lot of the storage, which saves both time and space).