This post is about some very simple category theory constructions and how one can model them in C++.
First a type for binary products.
template <class A, class B>
using product = std::pair<A, B>;
//`fst (x, y)` is the projection `x`
template <class A, class B>
inline auto fst (product<A, B> const& p) {
return p.first;
}
//`snd (x, y)` is the projection `y`
template <class A, class B>
inline auto snd (product<A, B> const& p) {
return p.second;
}
//`mk_product (a, b) computes the product of `a` and `b`
template <class A, class B>
inline product<A, B> mk_product (A&& a, B&& b) {
return std::make_pair (std::forward<A> (a), std::forward<B> (b));
}
Now $dup : X \rightarrow X \times X$ defined by $x \mapsto (x,\; x)$.
//`dup a` computes the product `(a, a)`
template <class A>
inline product<A, A> dup (A const& x) { return mk_product (x, x); }
Next up, $twist : X \times Y \rightarrow Y \times X$ defined by $(x,\; y) \mapsto (y,\; x)$.
//`twist (x, y)` is the product `(y, x)`
template <class A, class B>
inline product<B, A> twist (product<A, B> const& p) {
return mk_product (snd (p), fst (p));
}
If $f : U \rightarrow R$ and $g : V \rightarrow S$ then we have $ravel : U \times V \rightarrow R \times S$ defined by $(x,\; y) \mapsto (f (x),\; g (y))$.
//`ravel f g (x, y)` is the product `(f x, g y)` (credit to Max
//Skaller on the name)
auto ravel = [=](auto f) {
return [=](auto g) {
return [=](auto const& x) {
return mk_product (f (fst (x)), g (snd (x)));
};
};
};
If $X \times Y$ is a (binary) product with projections $\pi_{x}$ and $\pi_{y}$, $Z$ an object, morphisms $f : Z \rightarrow X$, $g : Z \rightarrow Y$ then $\left\langle f, g \right\rangle : Z \rightarrow X \times Y$ is the mediating arrow $z \mapsto (f (z),\;g (z))$.
//The product of morphisms <`f`, `g`> (see
//https://en.wikipedia.org/wiki/Product_(category_theory))
auto prod = [=](auto f, auto g) {
return [=](auto const& z) { return mk_product (f (z), g (z)); };
};
We can use the Pretty good sum type library to define a type suitable for modeling (binary) coproducts.
template <class A>
struct Left {
A a;
template <class U> explicit Left (U&& u) : a {std::forward<U> (u)} {}
A const& value () const { return a; }
};
template <class B>
struct Right {
B b;
template <class U> explicit Right (U&& u) : b {std::forward<U> (u)} {}
B const& value () const { return b; }
};
template <class A, class B>
using sum = pgs::sum_type<Left<A>, Right<B>>;
template <class> struct sum_fst_type;
template <class A, class B>
struct sum_fst_type<sum<A, B>> { using type = A; };
template <class S> struct sum_snd_type;
template <class A, class B>
struct sum_snd_type<sum<A, B>> { using type = B; };
template <class S>
using sum_fst_t = typename sum_fst_type<S>::type;
template <class S>
using sum_snd_t = typename sum_snd_type<S>::type;
If $X + Y$ is a (binary) sum with injections $i_{x}$ and $i_{y}$, $Z$ an object, morphisms $f : X \rightarrow Z$, $g : Y \rightarrow Z$ then $\left[ f, g \right] : X \times Y \rightarrow Z $ is the mediating arrow $\begin{align*} e \mapsto \begin{cases} f (e) & \text{if $e \in X$} \\ g (e) & \text{if $e \in Y$} \end{cases} \end{align*}$.
//The coproduct of morphisms [`f, `g`] (see
//https://en.wikipedia.org/wiki/Coproduct)
template <class S>
auto co_product = [=](auto f) {
return [=](auto g) {
return [=](S const& s) {
using A = sum_fst_t<S>;
using B = sum_snd_t<S>;
using lres_t = decltype (f (std::declval<A>()));
using rres_t = decltype (g (std::declval<B>()));
static_assert (
std::is_same<lres_t, rres_t>::value
, "co_product : result types differ");
using res_t = lres_t;
return s.match<lres_t>(
[=](Left<A> const& l) { return f (l.value ()); },
[=](Right<B> const& r) { return g (r.value ()); }
);
};
};
};
That's it. Here's some example usage of all this stuff.
auto succ=[](int i) { return i + 1; };
auto pred=[](int i) { return i - 1; };
auto twice=[](int i) { return 2 * i; };
auto square=[](int i) { return i * i; };
auto add=[](product<int, int> const& s) { return (fst (s) + snd (s)); };
//--
//Products
//`dup`
auto p = dup (1);
std::cout << p << std::endl; //Prints '(1, 1)'
//`prod`
p = prod (succ, pred) (4);
std::cout << p << std::endl; //Prints '(5, 3)'
//`twist`
p = twist (p);
std::cout << p << std::endl; //Prints '(3, 5)'
//`ravel`
p = ravel (succ) (pred) (p);
std::cout << p << std::endl; //Prints '(4, 4)'
//--
//Sums
sum<int, float> l{pgs::constructor<Left<int>>{}, 1};
sum<int, float> r{pgs::constructor<Right<float>>{}, 1.0f};
std::cout <<
co_product<sum<int, float>>
([=](int i) { return std::to_string(i); })
([=](float f) { return std::to_string(f); })
(l)
<< std::endl;
;//Prints '1'
std::cout <<
co_product<sum<int, float>>
([=](int i) { return std::to_string(i); })
([=](float f) { return std::to_string(f); })
(r)
<< std::endl;
;//Prints '1.000000'
//--
