Template metaprogramming VII: The Enemy Within

Remember where were we last time? We had this code to define a list:

struct NIL {
	typedef NIL Head;
	typedef NIL Tail;
};

template <typename H, typename T=NIL> struct Lst {
	typedef H Head;
	typedef T Tail;
};

template <int N> struct Int{ static const int result = N; };
typedef Lst< Int<1>, Lst< Int<2>, Lst< Int<3> > > > OneTwoThree;

Now, to increase our template-foo, let's practice some basic operations. The same operations you would implement to practice your skill any other functional language. If I remember correctly these where useful when learning Haskel: getting a list's lenght, getting the Nth element, appending and preppending elements... that sort of stuff.

Let's start with the most basic: getting the length of a list. We don't really have a for loop so using recursion is the only way. It gets easier if we think again on our definition of list: "think of a list as tuple, two elements, the first (called head) will be the first element of the list and the second element as another list or a NIL object". Whit this definition of a list, then it's length turns to be 1 (the head) + the length of the remaining list (the tail), with a special case for the length of a NIL object which should always be 0. In template-speak:

template <typename LST> struct Length {
	typedef typename LST::Tail Tail;
	static const unsigned int tail_length = Length< Tail >::result;
	static const unsigned int result = 1 + tail_length;
};

template <> struct Length <NIL> {
	static const unsigned int result = 0;
};

I know. You are thinking "wait, what?". Well, even for this basic case we need to use some esoteric language features:

• typename is needed to tell the compiler LST::Tail is a type and not a static variable (like Length::result is). Did you remember that from chapter IV?
• We have to use recursive templates, but you probably already figured that out. You should remember this from chapter II.
• We can provide a spetialization of a template. You should also remember this from chapter II.

Obviously, you can write it this way too:

template <typename LST> struct Length {
	static const unsigned int result = 1 + Length< typename LST::Tail >::result;
};

template <> struct Length  {
	static const unsigned int result = 0;
};

The rest of the "basic" list-operations are quite similar, but I'll leave that for another post.

---

Thank you Stéphane Michaut for pointing out typos and bugs in the code listings