## Friday, July 25, 2014

### Cartesian product (redux)

In this blog post we looked at programs to compute Cartesian Products. One algorithm (given here in OCaml) if you recall is
let prod l r =
let g acc a =
let f acc x =
(a, x) :: acc
in List.fold_left f acc r
in List.fold_left g [] l |> List.rev


In that earlier post I translated the above program into C++. This time I'm doing the same straightforward translation but using the Boost.MPL library to compute such products at compile time. It looks like this:

#include <boost/mpl/pair.hpp>
#include <boost/mpl/vector.hpp>
#include <boost/mpl/push_front.hpp>
#include <boost/mpl/fold.hpp>
#include <boost/mpl/reverse.hpp>
#include <boost/mpl/placeholders.hpp>

using namespace boost::mpl::placeholders;

template <class L, class R>
struct product
{
struct g {
template <class AccT, class A>
struct apply {
typedef typename boost::mpl::fold <
R, AccT
, boost::mpl::push_front<_1, boost::mpl::pair<A, _2> >
>::type type;
};
};

typedef typename boost::mpl::reverse <
typename boost::mpl::fold <
L, boost::mpl::vector<>, g>::type>::type type;
};

The translation proceeds almost mechanically! Does it work though? You betcha! Here's a test we can convince ourselves with:
#include <boost/mpl/equal.hpp>
#include <boost/mpl/for_each.hpp>
#include <boost/mpl/int.hpp>

#include <iostream>

using namespace boost::mpl;

typedef vector<int_<1>, int_<2> > A;
typedef vector<int_<3>, int_<4>, int_<5> > B;
typedef product <A, B>::type result;

BOOST_MPL_ASSERT((
equal<
result
, vector<
pair<int_<1>, int_<3> >
, pair<int_<1>, int_<4> >
, pair<int_<1>, int_<5> >
, pair<int_<2>, int_<3> >
, pair<int_<2>, int_<4> >
, pair<int_<2>, int_<5> >
>
> ));

struct print_class_name {
template <typename T>
void operator()( T t ) const {
std::cout << typeid(t).name() << " ";
}
};

int main ()
{
boost::mpl::for_each<result>(print_class_name());

return 0;
}

The takeaway is, learning yourself some functional programming is a great way to improve your template meta-programming fu! (That of course should come as no surprise... )