## Thursday, June 12, 2014

### 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!