### 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... )