Template metaprogramming VIII: A Rough Whimper of Insanity

Remember last time? We learned how to get the lenght of a list. This time I'll introduce some more of these basic ops. Let's begin with "Nth": getting the Nth element of a list; which, remember, in this case is a type, not a concrete element. This means the Nth element will be something like int, char, const char*, not 1, 2 or 3. We introduced a trick to get around this limitation before using a template , go there to refresh your memory if needed.

So, what would the coloquial definition of "Nth" be? I'd put it like "The operation Nth for a list equals the head of the list for N = 0 and Nth (minus one) of the tail otherwise". A little bit more formally:

Nth(0, lst) <- lst.head
Nth(n, lst) <- Nth(n-1, lst.tail)

Translating this to C++ should be a breeze to you now. Try it, I'll wait. Read? OK, this is MY answer:

template <typename LST, int N> struct Nth {
	typedef typename LST::Tail Tail;
	typedef typename Nth<Tail, N-1>::result result;
};

template <typename LST> struct Nth<LST, 0> {
	typedef typename LST::head result;
};

Though the structure is very similar to the previous "basic operation", getting the length of a list, the concept is quite different. This time we're defining a return type recursively. Anyway, it was too easy indeed, let's try a more complex operation now.

How can we check if an element exists on a list? Seems easy enough, an element is included in a list if the head equals the element itself or if the element is included in the tail. In the pseudo language I just invented:

Includes(lst.head, lst) <- true
Includes(e, lst) <- Includes(e, lst.tail)

Looks easy, right? Well, there's a bug there, can you spot it? Yeah, we're missing the false condition. We should add a third specialization:

Includes(lst.head, lst) <- true
Includes(e, NIL) <- false
Includes(e, lst) <- Includes(e, lst.tail)

Again, let's translate the pseudocode to C++. Try it, I'll wait. Read? OK, this is MY answer:

template <class Elm, class Lst>
struct Includes {
	typedef typename LST::head Head;
	typedef typename LST::tail Tail;

	static const bool found = (Elm == Head);
	static const bool found_tail = Includes<Elm, Tail>::result;
	static const bool result = found || found_tail;
};

template <class Elm> struct Includes <Elm, NIL> {
	static const bool result = false;
};

Looks nice, doesn't it? Too bad it won't work, you can't compare two types. What would (int == char) mean in C++? We need a helper there, some kind of trick to compare two types. We can use partial template specialization again:

template <class X, class Y>
struct Eq { static const bool result = false; }

template <class X>
struct Eq<X, X> { static const bool result = true; }

With this little struct now we can write our include operation this way:

template <class Elm, class Lst>
struct Includes {
	static const bool result = Eq<Elm, typename LST::head>::result
				   || Includes<Elm, typename LST::tail>::result;
};

template <class Elm> struct Includes<Elm, NIL> {
	static const bool result = false;
};

Very esoteric looking, the right mix of Haskel, C++ and booze to ensure job security for life. Next time we'll find a way to search for the position of an element, a somewhat more complicated task.