Earlier this week, I had a need for a recursive list, that is, a list defined in terms of itself. I think, "back in the day" implementing a data structure of that sort would have been a snap for the everyday C programmer. Today, in this modern C++ world I found myself struggling a little and came to think that maybe the old ways are fading :)

For motivation, here's a couple of examples of the sort of thing I'm talking about.

(1) The list `[0; 1; 0; 1; 0; 1; ...]`

is a list with a cycle in it. In OCaml you'd write that as `let rec l = 0 :: 1 :: l`

.

(2) An interpreter using the technique of environments and closures can require an environment (`(string * value) list`

) to contain a closure where the closure contains the environment. In OCaml you'd write `let rec vars = (tag, V_closure (vars, xpr)) :: !env; env := vars`

.

Of course with pointers, it's not hard to implement recursive structures in C++. The trouble is having to concern yourself with their memory management due to the absence of garbage collection.

Alright, here is what I came up with. The code is pretty short.

#include <boost/variant.hpp> #include <memory> #include <stdexcept> template <class T> struct node; template <class T> using node_ptr=typename node<T>::node_ptr; template <class T> using node_weak_ptr=typename node<T>::weak_ptr; template <class T> using node_shared_ptr=typename node<T>::shared_ptr; template <class T> struct ptr_t; template <class T> using list=ptr_t<node<T>>; template <class T> using list_ref=node_weak_ptr<T>; template <class T> list<T> nil (); template <class T> bool empty (list<T> l); template <class T> list<T> cons (T val, list<T> l); template <class T> T& hd (list<T> l); template <class T> list<T>& tl (list<T> l); template <class T> list_ref<T> ref (list<T> src); template <class T> bool is_ref (list<T> src);

The idea behind the implementation is generalize a pointer to node as a union with two variants, a shared pointer or a weak pointer.

template <class T> struct ptr_t : boost::variant <std::shared_ptr<T>, std::weak_ptr<T>> { typedef boost::variant <std::shared_ptr<T>, std::weak_ptr<T>> base; ptr_t () {} ptr_t (std::weak_ptr<T> p) : base (p) {} ptr_t (std::shared_ptr<T> p) : base (p) {} }; template <class T> struct node { typedef ptr_t<node> node_ptr; typedef std::weak_ptr<node> weak_ptr; typedef std::shared_ptr<node> shared_ptr; T data; node_ptr next; };

This little bit of implementation detail comes up a couple of times so it's handy to factor it out.

namespace { //'get' at the raw pointer in the union of a smart/weak pointer template <class T> T* get (ptr_t<T> l) { if (std::shared_ptr<T>* p= boost::get<std::shared_ptr<T>>(&l)) { return p->get (); } return boost::get<std::weak_ptr<T>>(l).lock ().get (); } }//namespace<anonymous>

The rest of the implementation is basically a set of "one-liners".

template <class T> list<T> nil (){ return node_shared_ptr<T> (); } template <class T> bool empty (list<T> l) { return (get (l)) == nullptr; } template <class T> list<T> cons (T val, list<T> l) { return node_shared_ptr<T> (new node<T>{val, l}); } template <class T> T& hd (list<T> l) { if (empty (l)) throw std::runtime_error ("hd"); return get (l) -> data; } template <class T> list<T>& tl (list<T> l) { if (empty (l)) throw std::runtime_error ("tl"); return get (l) -> next; } template <class T> bool is_ref (list<T> src) { return boost::get<list_ref<T>>(&src)!=nullptr; } template <class T> node_weak_ptr<T> ref (list<T> src) { return node_weak_ptr<T>(boost::get<node_shared_ptr<T>>(src)); }

OK, well, that's about it. Let's see, regarding usage, (1) could be expressed like this

list<int> l = cons (0, cons (1, nil<int> ())); tl (tl (l)) = ref (l);or, if we assume the existence of a 'last' function with an obvious definition, could be tidied up to read

list<int> l = cons (0, cons (1, nil<int> ())); tl (last (l)) = ref (l);and (2) can be stated like this

typedef std::pair<std::string, value_t> p_t; list<p_t> vars = node_shared_ptr<p_t>(new node<p_t>); hd (vars) = std::make_pair (tag, V_closure {ref (vars), xpr}); tl (vars) = *env; *env = vars;