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!
