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  struct LST {
	typedef H Head;
	typedef T Tail;
};

template  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  struct Length {
	typedef typename LST::Tail Tail;
	static const unsigned int tail_lenth = Length< Tail >::result;
	static const unsigned int result = 1 + tail_length;
};

template <> struct Length  {
	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  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.

Advertisements


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s