Alp Mestanogullari's Blog

Functional compile-time templates based type lists in C++

Posted in Uncategorized by alpmestan on 2009/12/03

Hi,

Have you ever heard about typelists in C++ ? That just consists in using the functional way of defining lists, but with templates.
It looks like that :

template <typename Head, typename Tail>
struct TypeList
{
  typedef Head head;
  typedef Tail tail;
};

However, we’ll need a type representing an empty type list. Ours will be the following.

struct EmptyList { };

How to write metafunctions (compile-time functions, working over types and not values — actually, the types are in this context like “values”) for these type lists now ?

Let’s start with a metafunction computing the length of a type list :

// declaration
template <typename Typelist>
struct Length;

// the normal case : the head element of the list (it's a type), and the tail, which is itself a type list
template <typename H, typename T>
struct Length<TypeList<H, T> >
{
  static const int value = 1 + Length<T>::value ;
};

// the terminal case : our typelist is the empty list, we're at the end of the list, so we won't add 1 neither we will go on with the recursion
template <>
struct Length<EmptyList>
{
  static const int value = 0 ;
};

Now, calling it on a given typelist will return us the good result :

Length< TypeList<int, TypeList<char, TypeList<bool, EmptyList> > > >::value // equals 3

Do you want more ? I guess you do, of course. Let’s tackle a more complicated one : Map. It maps a type list to another one, computing the result of the application of a metafunction on each type of the type list. Ok, let’s start with the declaration.

template <typename TL, template <typename> class Func>
struct Map;

Now, the basical case, with a head element and the tail, will consist in computing the result of the application of the metafunction of the head element, and appending to it the result of Map on the tail. Looks like that :

template <typename H, typename T, template <typename> class Func>
struct Map<TypeList<H, T>, Func>
{
  typedef TypeList< typename Func<H>::type, typename Map<T, Func>::type > type;
};

And the trivial case, on the empty list :

template <template <typename> class Func>
struct Map<EmptyList, Func>
{
  typedef EmptyList type;
};

And we’re done with Map !

Let’s see one more interesting function over type lists : Filter. It’ll filter (really ?!) the type list according to a compile-time predicate, and return the original type list without the types that didn’t match the predicate.
Here we go !

template <typename TypeList, template <typename> class Pred>
struct Filter;

template <typename H, typename T, template <typename> class Pred, bool result>
struct FilterAux
{
  typedef typename Filter<T, Pred>::type type;
};

template <typename H, typename T, template <typename> class Pred>
struct FilterAux<H, T, Pred, true>
{
  typedef TypeList<H, typename Filter<T, Pred>::type> type;
};

template <typename H, typename T, template <typename> class Pred>
struct Filter<TypeList<H, T>, Pred>
{
  typedef typename FilterAux<H, T, Pred, Pred<H>::value>::type type;
};

template <template <typename> class Pred>
struct Filter<EmptyList, Pred>
{
  typedef EmptyList type;
};

This one was trickier, because we needed an auxiliary template structure to have a bool against which we could specialize, to either go on without keeping the type in the type list (in case it doesn’t match the predicate) or keeping it.

Now, I’ll leave as exercise the following functions :
– Repeat : takes a type, a number, and returns a type list containing n times the given type
– Take : takes a type list and a number, and returns a type list contaning the first n elements of the typelist if possible, less otherwise.
– Interleave : it takes 2 two lists, say l1 = [T1, T2, T3] and l2 = [U1, U2, U3] and returns the list [T1, U1, T2, U2, T3, U3]
– Zip : takes two lists and returns a list of component-wise pairs of the types
– ZipWith : takes two lists and a function itself taking two types and returning a type, and returns a list compound of the component-wise application of the given function on both lists simultaneously

I’ll try to post these during the upcoming days.

Good functional metaprogramming to all ;)

About these ads
Tagged with: , ,

5 Responses

Subscribe to comments with RSS.

  1. uberVU - social comments said, on 2009/12/03 at 11:37 am

    Social comments and analytics for this post…

    This post was mentioned on Twitter by alpmestan: Functional compile-time templates based type lists in C++: http://wp.me/pEB41-17

  2. Goten said, on 2009/12/03 at 6:14 pm

    Nice job dude,

    Despite I was already using typelists it’s always a pleasure to read you :p.
    Your examples of algorithms on typelists are clearly oriented haskell-like array function. It’s really interesting for the algorithm part. You also could have write about typeAt or replace algorithms which can be really useful when you use Typelist.
    At last, you could have explain for what typelist are useful (like emulating variadic templates).
    But again it’s really great, looking forward for new articles, thanks.

  3. 3DArchi said, on 2009/12/12 at 5:49 pm

    Hi,
    Great, as usual !
    I am just wondering if you have ever used or known about someone who have used functional paradigm either with C++ templates or with a dedicated language in a ‘real-life’ project (that is to say, not a research one). I don’t still manage to see what to do with that ?

  4. alpmestan said, on 2009/12/13 at 4:59 pm

    Hi,

    @Goten : I’ve only implemented typelists like lists are implemented in Haskell, thus providing the functions we use the most in Haskell. I didn’t want my code to be a copy of Andrei Alexandrescu’s one in Modern C++ Design. That’s all.

    @3DArchi : You can find many such projects. For example, there is a SCM written in Haskell, a Window Manager for Linux, 3D games, Linux kernel modules, etc etc.
    You really should consider browsing the Haskell wiki on the “real world functional programming” pages. And by the way, using FP over C++ templates is basically what boost.mpl, boost.fusion and all do. Since there are no side effects at compile-time, and that we use functional structures, all we do with C++ templates is functional programming :)

  5. matthieubrucher said, on 2010/03/26 at 3:13 pm

    I do that a lot in my professionnal code. A lot of typelists with the types being class with some static functions that will be called to initialize a bunch of variables. This indeed helps a lot for robustness and beautifulness!


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

Follow

Get every new post delivered to your Inbox.

Join 251 other followers

%d bloggers like this: