Implementing meta-function zip in c++11

Question

I am actually trying to see if I can get a minimal library that supports the very few operations I use from boost::fusion.

Here is what I have so far...

template < typename... Types >
struct typelist
{
};

template < template < typename... > class F, typename... Args >
struct apply
{
  typedef typename F < Args... >::type type;
};

template < typename, template < typename... > class >
struct foreach;

template < typename... Types, template < typename Arg > class F >
struct foreach < typelist < Types... >, F >
{
  typedef typelist < typename apply < F, Types >::type... > type; 
};

Since the meta-function foreach implementation is trivial, I thought zip would be easy too. Apparently, this is not the case.

template < typename... >
struct zip;

template < typename...  Types0, typename... Types1 >
struct zip < typelist < Types0... >, typelist < Types1... > >
{
  typedef typelist < typelist < Types0, Types1 >... > type;
};

How can I generalize this zip meta-function to arbitrary number of typelists? What we need here seems to be a parameter pack of parameter packs. I am not sure how to do that.

Edit 1:

Implementation of is_equal...

template < std::size_t... Nn >
struct is_equal;

template < std::size_t N0, std::size_t N1, std::size_t... Nn >
struct is_equal < N0, N1, Nn... >
: and_ <
    typename is_equal < N0, N1 >::type
  , typename is_equal < N1, Nn... >::type
  >::type
{
};

template < std::size_t M, std::size_t N >
struct is_equal < M, N > : std::false_type
{
  typedef std::false_type type;
};

template < std::size_t N >
struct is_equal < N, N > : std::true_type
{
  typedef std::true_type type;
};

A similar approach can be taken to zip as well I think... haven't tried with zip yet, but will do so when I get back home.

Edit 2:

Here is what I finally thought looked more elegant. This is basically a variation of Vaughn Cato's approach.

namespace impl
{

template < typename Initial, template < typename, typename > class F, typename... Types >
struct foldl;

template < typename Initial, template < typename, typename > class F, typename First, typename... Rest >
struct foldl < Initial, F, First, Rest... >
{
  typedef typename foldl < typename F < Initial, First >::type, F, Rest... >::type type;
};

template < typename Final, template < typename, typename > class F >
struct foldl < Final, F >
{
  typedef Final type;
};

template < typename Type, typename TypeList >
struct cons;

template < typename Type, typename... Types >
struct cons < Type, typelist < Types... > >
{
  typedef typelist < Types..., Type > type;
};

template < typename, typename >
struct zip_accumulator;

template < typename... Types0, typename... Types1 >
struct zip_accumulator < typelist < Types0... >, typelist < Types1... > >
{
  typedef typelist < typename cons < Types1, Types0 >::type... > type;
};

template < typename... Types0 >
struct zip_accumulator < typelist <>, typelist < Types0... > >
{
  typedef typelist < typelist < Types0 >... > type;
};

template < typename... TypeLists >
struct zip
{
  typedef typename foldl < typelist <>, zip_accumulator, TypeLists... >::type type;
};

}

template < typename... TypeLists >
struct zip
{
  static_assert(and_ < typename is_type_list < TypeLists >... >::value, "All parameters must be type lists for zip");
  static_assert(is_equal < TypeLists::length... >::value, "Length of all parameter type lists must be same for zip");
  typedef typename impl::zip < TypeLists... >::type type;
};

template < typename... TypeLists >
struct zip < typelist < TypeLists... > > : zip < TypeLists... >
{
};

This treats zip as a fold operation.

Is that really a zip? I thought a zip would look more like `typelist...>` (can be generalized to take any metafunction other than `pair`). — Luc Danton, Sep 24 '11 at 15:03
@LucDanton: You are right. I have corrected the `zip` implementation. `typelist` is the generalized `pair` meta-function. But how do I pass the arbitrary number of parameter packs? — zrb, Sep 24 '11 at 15:12
@GregoryPakosz: If this can be done without boiler plate, it will be awsome. — zrb, Sep 24 '11 at 15:16
`zip, typelist>::type` is `typelist, typelist>`. That's not so much a `zip` as a `cons`, sort of, not really. What I suggested is `typelist...>`, which yields `typelist, typelist, typelist>`. — Luc Danton, Sep 24 '11 at 15:17
Shouldn’t `apply` (= `map`) yield a template with template arguments `, F, F… >` instead of `F` as it doesn now? — Konrad Rudolph, Sep 24 '11 at 15:17
@LucDanton: You are right. I have corrected the `zip` implementation again. — zrb, Sep 24 '11 at 15:33
@KonradRudolph: The `apply` would be called with something like `add_pointer`. I now think that `transform` is a better name than `foreach`. — zrb, Sep 24 '11 at 15:35

Vaughn Cato · Accepted Answer · 2011-09-25T05:27:44.977

6

This is the shortest implementation I've discovered:

template <typename...> struct typelist { };   
template <typename A,typename B> struct prepend;
template <typename A,typename B> struct joincols;
template <typename...> struct zip;    

template <typename A,typename... B>
struct prepend<A,typelist<B...> > {
  typedef typelist<A,B...> type;
};

template <>
struct joincols<typelist<>,typelist<> > {
  typedef typelist<> type;
};

template <typename A,typename... B>
struct joincols<typelist<A,B...>,typelist<> > {
  typedef typename
    prepend<
      typelist<A>,
      typename joincols<typelist<B...>,typelist<> >::type
    >::type type;
};

template <typename A,typename... B,typename C,typename... D>
struct joincols<typelist<A,B...>,typelist<C,D...> > {
  typedef typename
    prepend<
      typename prepend<A,C>::type,
      typename joincols<typelist<B...>,typelist<D...> >::type
    >::type type;
};

template <>
struct zip<> {
  typedef typelist<> type;
};

template <typename A,typename... B>
struct zip<A,B...> {
  typedef typename joincols<A,typename zip<B...>::type>::type type;
};

edited Sep 25 '11 at 05:27

answered Sep 25 '11 at 05:22

Vaughn Cato

63,448
5
82
132

1

+1 for avoiding `enable_if` and `gcc_workaround` and relying purely on template pattern matching. I think I see some patterns emerging from this. I am adding the implementation of a `is_equal` meta-function that I used with `zip` to ensure that all its parameter `typelists` had the same length. – zrb Sep 26 '11 at 07:00
Can you please explain me what is zip meta function? and this [question](http://stackoverflow.com/questions/11397484/variadic-template-no-matching-function-call) also related to zip meta function?. Thanks – Mr.Anubis Jul 10 '12 at 17:22
@Mr.Anubis: Here's a pretty good answer: http://stackoverflow.com/questions/1115563/what-is-zip-functional-programming – Vaughn Cato Jul 10 '12 at 22:00

Luc Danton · Answer 2 · 2011-09-24T16:42:48.103

Seems to be doable with fully-fledged lists (that means head, tail and cons operations) and recursion. Tested with a snapshot of GCC 4.7, all the std stuff is from <type_traits>:

struct nil {};

template<typename T>
struct is_nil: std::is_same<T, nil> {};

template<typename... T>
struct and_: std::true_type {};

template<typename First, typename... Rest>
struct and_<First, Rest...>
: std::integral_constant<
    bool
    , First::value && and_<Rest...>::value
> {};

template<typename T>
struct not_
: std::integral_constant<bool, !T::value> {};

template<typename... T>
struct typelist;

template<typename First, typename Second, typename... Rest>
struct typelist<First, Second, Rest...> {
    typedef First head;
    typedef typelist<Second, Rest...> tail;
};

template<typename Last>
struct typelist<Last> {
    typedef Last head;
    typedef nil tail;
};

template<typename T, typename List>
struct cons;

template<typename T, typename... Ts>
struct cons<T, typelist<Ts...>> {
    typedef typelist<T, Ts...> type;
};

// workaround for:
// sorry, unimplemented: cannot expand '...' into a fixed-length argument list
template<template<typename...> class Template, typename... T>
struct gcc_workaround {
    typedef Template<T...> type;
};

namespace detail {

template<typename Sfinae, typename... Lists>
struct zip;

template<typename... Lists>
struct zip<
    typename std::enable_if<and_<is_nil<typename Lists::tail>...>::value>::type
    , Lists...
> {
    typedef typelist<typelist<typename Lists::head...>> type;
};

template<typename... Lists>
struct zip<
    typename std::enable_if<and_<not_<is_nil<typename Lists::tail>>...>::value>::type
    , Lists...
> {
    typedef typename cons<
        typelist<typename Lists::head...>
        , typename gcc_workaround<zip, void, typename Lists::tail...>::type::type
    >::type type;
};

} // detail

template<typename... Lists>
struct zip: detail::zip<void, Lists...> {};

You might want to add error checking to all this (I'm thinking of invalid instantiations that are currently simply left as incomplete types). Frankly given the amount of time it took me to figure this out, I'd suggest sticking with Boost.MPL. Things like lazy evaluation (with which I wouldn't have needed to do the SFINAE stuff) are a boon and I'd don't like reinventing them. Plus the day it's C++11 enabled you reap the best of both worlds.

I forgot to mention that Boost.MPL also has the advantages of genericity. It can work on any type that satisfies one of its sequence concept (it's also possible to non-intrusively adapt a preexisting type), whereas you force the use of typelist.

Implementing the `typelist` type as a cons list gets the job done. I was wondering if it can be done without resorting to this. — zrb, Sep 24 '11 at 16:52

Implementing meta-function zip in c++11

2 Answers2

Linked