How to create the Cartesian product of a type list?

I'd like to create the cross product of a list of types using variadic templates.

Here's what I have so far:

#include <iostream>
#include <typeinfo>
#include <cxxabi.h>

template<typename...> struct type_list {};

template<typename T1, typename T2> struct type_pair {};

template<typename T, typename... Rest>
  struct row
{
  typedef type_list<type_pair<T,Rest>...> type;
};

template<typename... T>
  struct cross_product
{
  typedef type_list<typename row<T,T...>::type...> type;
};

int main()
{
  int s;
  typedef cross_product<int, float, short>::type result;
  std::cout << abi::__cxa_demangle(typeid(result).name(), 0, 0, &s) << std::endl;

  return 0;
}

This program outputs:

$ g++ -std=c++0x cross_product.cpp ; ./a.out 
type_list<type_list<type_pair<int, int>, type_pair<int, float>, type_pair<int, short> >, type_list<type_pair<float, int>, type_pair<float, float>, type_pair<float, short> >, type_list<type_pair<short, int>, type_pair<short, float>, type_pair<short, short> > >

But I'd like it to output:

type_list<type_pair<int,int>, type_pair<int,float>, type_pair<int,short>, type_pair<float,int>,...>

That is, without the nested type_lists.

Is there a direct way to do this without the row helper, or should the solution "unwrap" the nested type_lists somehow?

Solution 1:

A nice clean version I think:

cross_product.cpp:

#include "type_printer.hpp"

#include <iostream>

template<typename ...Ts> struct type_list {};
template<typename T1, typename T2> struct pair {};

// Concatenation
template <typename ... T> struct concat;
template <typename ... Ts, typename ... Us>
struct concat<type_list<Ts...>, type_list<Us...>>
{
    typedef type_list<Ts..., Us...> type;
};

// Cross Product
template <typename T, typename U> struct cross_product;

// Partially specialise the empty case for the first type_list.
template <typename ...Us>
struct cross_product<type_list<>, type_list<Us...>> {
    typedef type_list<> type;
};

// The general case for two type_lists. Process:
// 1. Expand out the head of the first type_list with the full second type_list.
// 2. Recurse the tail of the first type_list.
// 3. Concatenate the two type_lists.
template <typename T, typename ...Ts, typename ...Us>
struct cross_product<type_list<T, Ts...>, type_list<Us...>> {
    typedef typename concat<
        type_list<pair<T, Us>...>,
        typename cross_product<type_list<Ts...>, type_list<Us...>>::type
    >::type type;
};

struct A {};
struct B {};
struct C {};
struct D {};
struct E {};
struct F {};

template <typename T, typename U>
void test()
{
    std::cout << print_type<T>() << " \u2a2f " << print_type<U>() << " = "
        << print_type<typename cross_product<T, U>::type>() << std::endl;
}

int main()
{
    std::cout << "Cartesian product of type lists\n";
    test<type_list<>, type_list<>>();
    test<type_list<>, type_list<A>>();
    test<type_list<>, type_list<A, B>>();
    test<type_list<A, B>, type_list<>>();
    test<type_list<A>, type_list<B>>();
    test<type_list<A>, type_list<B, C, D>>();
    test<type_list<A, B>, type_list<B, C, D>>();
    test<type_list<A, B, C>, type_list<D>>();
    test<type_list<A, B, C>, type_list<D, E, F>>();
    return 0;
}

type_printer.hpp:

#ifndef TYPE_PRINTER_HPP
#define TYPE_PRINTER_HPP

#include "detail/type_printer_detail.hpp"

template <typename T>
std::string print_type()
{
    return detail::type_printer<T>()();
}

#endif

detail/type_printer_detail.hpp:

#ifndef DETAIL__TYPE_PRINTER_DETAIL_HPP
#define DETAIL__TYPE_PRINTER_DETAIL_HPP

#include <typeinfo>
#include <cxxabi.h>
#include <string>

template <typename ...Ts> struct type_list;
template <typename T1, typename T2> struct pair;

namespace detail {

// print scalar types
template <typename T>
struct type_printer {
    std::string operator()() const {
        int s;
        return abi::__cxa_demangle(typeid(T).name(), 0, 0, &s);
    }   
};

// print pair<T, U> types
template <typename T, typename U>
struct type_printer<pair<T, U>> {
    std::string operator()() const {
        return "(" + type_printer<T>()() + "," + type_printer<U>()() + ")";
    }   
};

// print type_list<T>
template <>
struct type_printer<type_list<>> {
    std::string operator()() const {
        return "\u2205";
    }   
};

template <typename T>
struct type_printer<type_list<T>> {
    std::string operator()() const {
        return "{" + type_printer<T>()() + "}";
    }   
    std::string operator()(const std::string& sep) const {
        return sep + type_printer<T>()();
    }   
};

template <typename T, typename ...Ts>
struct type_printer<type_list<T, Ts...>> {
    std::string operator()() const {
        return "{" + type_printer<T>()() + type_printer<type_list<Ts...>>()(std::string(", ")) + "}";
    }   
    std::string operator()(const std::string& sep) const {
        return sep + type_printer<T>()() + type_printer<type_list<Ts...>>()(sep);
    }   
};
}

#endif

Run:

g++ -std=c++0x cross_product.cpp && ./a.out

Output:

Cartesian product of type lists
∅ ⨯ ∅ = ∅
∅ ⨯ {A} = ∅
∅ ⨯ {A, B} = ∅
{A, B} ⨯ ∅ = ∅
{A} ⨯ {B} = {(A,B)}
{A} ⨯ {B, C, D} = {(A,B), (A,C), (A,D)}
{A, B} ⨯ {B, C, D} = {(A,B), (A,C), (A,D), (B,B), (B,C), (B,D)}
{A, B, C} ⨯ {D} = {(A,D), (B,D), (C,D)}
{A, B, C} ⨯ {D, E, F} = {(A,D), (A,E), (A,F), (B,D), (B,E), (B,F), (C,D), (C,E), (C,F)}

(I noticed on Windows using Chrome that the cross product unicode character is not coming out well. Sorry, I don't know how to fix that.)

Solution 2:

Somehow my brain is fried: I think I'm using more code than is needed but, at least, it has the desired results (although I didn't fix the memory leak):

#include <iostream>
#include <typeinfo>
#include <cxxabi.h>

template<typename...> struct type_list {};

template<typename T1, typename T2> struct type_pair {};

template<typename T, typename... Rest>
  struct row
{
  typedef type_list<type_pair<T,Rest>...> type;
};

template <typename... T> struct concat;
template <typename... S, typename... T>
struct concat<type_list<S...>, type_list<T...>>
{
    typedef type_list<S..., T...> type;
};

template <typename... T>
struct expand
{
    typedef type_list<T...> type;
};
template <> struct expand<> { typedef type_list<> type; };
template <typename... T, typename... L>
struct expand<type_list<T...>, L...>
{
    typedef typename concat<typename expand<T...>::type, typename expand<L...>::type>::type type;
};

template<typename... T>
  struct cross_product
{
    typedef typename expand<type_list<typename row<T,T...>::type...>>::type type;

};

int main()
{
  int s;
  typedef cross_product<int, float, short>::type result;
  std::cout << abi::__cxa_demangle(typeid(result).name(), 0, 0, &s) << std::endl;

  return 0;
}

Solution 3:

Maybe something like this:

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

template <typename S, typename T> struct typelist_cat;

template <typename ...Ss, typename ...Ts>
struct typelist_cat<typelist<Ss...>, typelist<Ts...>>
{
    typedef typelist<Ss..., Ts...> type;
};


template <typename S, typename T> struct product;

template <typename S, typename ...Ss, typename ...Ts>
struct product<typelist<S, Ss...>, typelist<Ts...>>
{
    // the cartesian product of {S} and {Ts...}
    // is a list of pairs -- here: a typelist of 2-element typelists
    typedef typelist<typelist<S, Ts>...> S_cross_Ts;

    // the cartesian product of {Ss...} and {Ts...} (computed recursively)
    typedef typename product<typelist<Ss...>, typelist<Ts...>>::type
        Ss_cross_Ts;

    // concatenate both products
    typedef typename typelist_cat<S_cross_Ts, Ss_cross_Ts>::type type;
};

// end the recursion
template <typename ...Ts>
struct product<typelist<>, typelist<Ts...>>
{
    typedef typelist<> type;
};

Now you should be able to use product<typelist<A,B,C>, typelist<D,E,F>>::type.