Implementing the idea of category in C++ at compile time

121 views Asked by At

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?

0

There are 0 answers