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:

	template<typename T>
	struct ConsNode {
	public:
	ConsNode(T car=T(), ConsList<T> cdr=ConsList<T>()):_car(car),_cdr(cdr) {}
	private:
	T _car;
	ConsList<T> _cdr;
	friend T car<>(const ConsList<T> &l);
	friend const ConsList<T>& cdr<>(const ConsList<T> &l);
	};

view raw 1_ConsNode.cpp hosted with ❤ by GitHub

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

	template <typename T>
	using ConsList= std::shared_ptr<ConsNode <T> >;

view raw 2_ConsList.cpp hosted with ❤ by GitHub

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:

	template<typename T>
	ConsList<T> cons(T car, const ConsList<T>& cdr=ConsList<T>()) {
	return std::make_shared<ConsNode<T> > (car,cdr);
	}

view raw 3_cons.cpp hosted with ❤ by GitHub

And car, cdr and isEmpty are simply defined as:

	template<typename T>
	T car(const ConsList<T>&l)
	{
	return l->_car;
	}
	template<typename T>
	const ConsList<T>& cdr(const ConsList<T>&l)
	{
	return l->_cdr;
	}
	template<class T>
	bool isEmpty(const ConsList<T>&l)
	{
	return !l;
	}

view raw car_cdr_isEmpty.cpp hosted with ❤ by GitHub

For convenience, we can define an operator<< ; notice we're using car, cdr and isEmpty, and using recursion.

	template<class T>
	std::ostream& operator<<(std::ostream& o, const ConsList<T>&l)
	{
	if(!isEmpty(l))
	o << car(l) << " " << cdr(l);
	return o;
	}

view raw operator.cpp hosted with ❤ by GitHub

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

	template<typename T>
	unsigned len(const ConsList<T>&l)
	{
	if(!isEmpty(l))
	return 0;
	return 1+len(cdr(l));
	}
	template<typename T>
	T sum(const ConsList<T>& l)
	{
	if(isEmpty(l))
	return 0;
	return car(l)+sum(cdr(l));
	}

view raw other_functions.cpp hosted with ❤ by GitHub

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

	int main(void)
	{
	ConsList<int> l=cons(3,cons(4,cons(7)));
	ConsList<int> l2=cons(9,cons(5,l)); // l2 shares the last 3 elements with l
	ConsList<int> l3=cons(11,cdr(l2)); // l3 shares with l2, and also with l
	cout << car(l) << " " << car(cdr(l)) << endl;
	cout << len(l2) << " " << sum(l2) << endl;
	cout << l2 << endl;
	cout << l3 << endl;
	}

view raw main.cpp hosted with ❤ by GitHub