SciTech.blog
SciTech.blog

Monads in C++

15 Oct 2017, 17:02 • monads, c++

Implementing monads in C++ is a little tricky, since there are no higher-kinded types. We can however use template specialisation to achieve the same effect.

In dynamically typed languages, implementing generic monads is simple (see in Python). In C++, it’s a little harder but it’s possible and we can have monads with all the useful static type checks.

Since C++ has no higher-kinded types, we’ll have to use template specialisation to override monadic operations:

template<template<typename> class M, typename T, typename U> struct Fmap {
    std::function<U(const T&)> f;
    auto operator()(const M<T>&) const;
};

template<template<typename> class M, typename T, typename U> struct Bind {
    std::function<M<U>(const T&)> f;
    auto operator()(const M<T>& m) const;
};

template<template<typename> class M, typename T> struct Join {
    auto operator()(const M<M<T>>&) const;
};

template<template<typename> class M, typename T, typename U> auto Fmap<M,T,U>::operator()(const M<T>& m) const {
    return Bind<M,T,U>{[&](auto x) { return M<U>{f(x)}; }}(m);
}

template<template<typename> class M, typename T, typename U> auto Bind<M,T,U>::operator()(const M<T>& m) const {
    return Join<M,T>{}(Fmap<M,T,M<U>>{f}(m));
}

template<template<typename> class M, typename T> auto Join<M,T>::operator()(const M<M<T>>& m) const {
    return Bind<M,M<T>,T>{[](auto x) { return x; }}(m);
}

template<template<typename> class M, typename T> class Monad {
public:
    template<typename U> auto fmap(const std::function<U(const T&)>& f) const {
        return Fmap<M,T,U>{f}(*static_cast<const M<T>*>(this));
    }
    template<typename U> auto bind(const std::function<M<U>(const T&)>& f) const {
        return Bind<M,T,U>{f}(*static_cast<const M<T>*>(this));
    }
};

Note that the Monad class isn’t really needed, but it provides useful convenience methods so we don’t have to explicitly list all the template arguments that are typically clear from context.

Using the above code, continuations can be implemented as follows:

template<typename T> class Cont : public Monad<Cont,T> {
    std::function<std::any(const std::function<std::any(const T&)>&)> fn;
public:
    Cont(const decltype(fn)& f) : fn(f) {}
    Cont(T&& x) : fn([x](auto f) { return f(x); }) {}
    std::any operator()(const std::function<std::any(const T&)>& f) const { return fn(f); }
};

template<typename T, typename U> struct Bind<Cont,T,U> {
    std::function<Cont<U>(const T&)> f;
    auto operator()(const Cont<T>& m) {
        auto f = this->f;
        return Cont<U>{[m,f](auto g) {
            return m([g,f](auto x) { return f(x)(g); });
        }};
    }
};

We only need to implement bind, since both fmap and join can be expressed in terms of bind. As an exercise, you might want to implement the List monad. If you implement fmap and join, you’ll get bind for free.

Comments

Name:

(Adi Shavit) • 7 Nov 2017, 17:06
Hi, Cool blog and cool posts! TBH, the code colors are horrendous - please try something else or a proper CSS! Moreover, please join the #fp channel discussions on the C++ Slack :-) Keep up this great content! Adi