### Cartesian product

For two sets $A$ and $B$, the Cartesian product denoted $A \times B$ is defined as the set of all ordered pairs $(a, b)$ where $a \in A$ and $b \in B$. The obvious algorithm to compute a Cartesian product in OCaml can is simple!

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

A straight-forward translation of the above program into C++ yields this.

#include <boost/range.hpp> #include <numeric> #include <iterator> template <class T> struct _inner { T a; _inner (T a) : a (a) {} template <class ItT> ItT operator ()(ItT acc, T const& x) const { return *acc++ = std::make_pair (a, x); } }; template <class T> _inner<T> inner (T a) { return _inner<T> (a); } template <class RangeT> struct _outer { RangeT r; _outer (RangeT r) : r (r){} template <class T, class ItT> ItT operator ()(ItT acc, T const& a) const { return std::accumulate ( boost::begin (r), boost::end(r), acc, inner (a)); } }; template <class RangeT> _outer<RangeT> outer (RangeT r) { return _outer<RangeT>(r); } template <class R1, class R2, class ItT> ItT prod (R1 A, R2 B, ItT dst) { return std::accumulate ( boost::begin (A), boost::end (A), dst, outer (B)); }

That's a **lot** more code than in the original OCaml program. But wait... C++11 lambda expressions to the rescue! We can eliminate most of that 'extra' code recovering the elegance of the original.

template <class R1, class R2, class ItT> ItT prod (R1 A, R2 B, ItT dst) { typedef ItT iterator; typedef boost::range_value<R1>::type alpha; typedef boost::range_value<R2>::type beta; return std::accumulate ( boost::begin (A), boost::end (A), dst, [=] (iterator acc, alpha const& a) { return std::accumulate ( boost::begin (B), boost::end (B), acc, [=] (ItT acc, beta const& x) { return *acc++ = std::make_pair (a, x); }); }); }

Now, my buddy Juan Alday tells me that we can expect more improvements in C++14 relating to lambdas. I hope to persuade him to write more about that here in the next couple of weeks. Stay tuned!

**Update:**
Juan advises that with C++ 14 'generic' lambdas, we can further get it down to this.

auto prod = [](auto const& A, auto const& B, auto dst) { return std::accumulate(std::begin(A), std::end(A), dst, [&B](auto& output, auto valA) { return std::accumulate(std::begin(B), std::end(B), output, [&valA](auto& output, auto valB) { std::get<0>(*output) = std::move(valA); std::get<1>(*output) = std::move(valB)); return ++output;}); }); };That's kind of amazing... There's not even one occurrence of the

`template`

keyword in that code!