I'm trying to play around with implementing the idea of category (as in Category Theory) in C++. I'm not sure it's possible but here is an implementation that for examples allows you define a category.
#include <functional>
#include <stdexcept>
#include <vector>
// A category is formed by:
// - A collection of objects
// - A collection of arrows, such that each arrow has a source object and a target object
// - A composition law for arrows that is associative
// - An identity arrow for each object
template <typename Object, typename Arrow>
struct Category {
std::function<Object(Arrow)> source;
std::function<Object(Arrow)> target;
std::function<Arrow(Object)> identity;
std::function<Arrow(Arrow, Arrow)> compose;
};
namespace FiniteSet
{
// An arrow in the category of finite sets is a triple (domains set, codomain set, function)
template <typename T>
struct Arrow {
std::vector<T> source;
std::vector<T> target;
std::function<T(T)> function;
};
template <typename T>
Arrow<T> identity(std::vector<T> set) {
return Arrow<T>{set, set, [](T x) { return x; }};
}
template <typename T>
Arrow<T> compose(Arrow<T> f, Arrow<T> g) {
if (f.source != g.target) {
throw std::runtime_error("Composition is not defined");
};
// We follow the right-to-left convention
return Arrow<T>{f.source, g.target, [f, g](T x) { return f.function(g.function(x)); }};
}
template <typename T>
std::vector<T> source(Arrow<T> f) { return f.source; }
template <typename T>
std::vector<T> target(Arrow<T> f) { return f.target; }
}
int main ()
{
auto finset = Category<std::vector<int>, FiniteSet::Arrow<int>>{
FiniteSet::source<int>,
FiniteSet::target<int>,
FiniteSet::identity<int>,
FiniteSet::compose<int>
};
}
This allows you to define the notion of a category (e.g. the category of finite sets of integers) at runtime, however this doesn't need to be the case since all information is available before compilation.
How can I implement the same idea at compile time (ideally by allowing to define something like a FiniteSet<int>)? Would it be possible to do this using templates + C++20 concepts?