## Saturday, July 23, 2016

### Simple category theory constructions

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{ife \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'

//--