Monads in C++ via static polymorphism

C++ isn't a functional language but it has a strong type template system, which allows us to easily implement generic monads via template specialisation. We'll define unit, bind, fmap and join as static methods of templated types.

template<template<typename> class F, typename T>
struct Unit {
    static F<T> apply(T x);
};

template<template<typename> class F, typename T, typename U>
struct Bind {
    static F<U> apply(const F<T>& obj, const std::function<F<U>(T)>& f);
};

template<template<typename> class F, typename T, typename U>
struct Fmap {
    static F<U> apply(const F<T>& obj, const std::function<U(T)>& f);
};

template<template<typename> class F, typename T>
struct Join {
    static F<T> apply(const F<F<T>>& obj);
};

Note that the type parameter F is higher-kinded for it's itself a template. The well-known generic implementations of the static methods are as follows:

template<template<typename> class F, typename T, typename U>
F<U> Bind<F,T,U>::apply(const F<T>& obj, const std::function<F<U>(T)>& f) {
    return Join<F,F<U>>::apply(Fmap<F,T,F<U>>::apply(obj, f));
}

template<template<typename> class F, typename T, typename U>
F<U> Fmap<F,T,U>::apply(const F<T>& obj, const std::function<U(T)>& f) {
    return Bind<F,T,U>::apply(obj, [f](auto x) { return Unit<F,U>::apply(f(x)); });
}

template<template<typename> class F, typename T>
F<T> Join<F,T>::apply(const F<F<T>>& obj) {
    return Bind<F,F<T>,T>::apply(obj, [](const F<T>& x) { return x; });
}

bind is thus defined by means of fmap and join, fmap using unit and bind and join using bind applied to an identity function.

We now have the underlying mechanism implemented but the syntax isn't particularly concise. To facilitate the use of the code we'll define an abstract Monad type:

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

This helper type doesn't add any new functionality but makes the code a little nicer. As an example, let's implement a List type on top of std::vector:

template<typename T>
struct List : Monad<List,T> {
    std::vector<T> vec;
    List(const std::vector<T>& v) : vec(v) {}
    List(T x) : vec({x}) {}
};

template<typename T>
struct Unit<List,T> {
    static List<T> apply(T x) { return List<T>{x}; }
};

template<typename T, typename U>
struct Bind<List,T,U> {
    static List<U> apply(const List<T>& l, const std::function<List<U>(T)>& f) {
        std::vector<U> v;
        for (const auto& el : l.vec) {
            for (const auto& el2 : f(el).vec) {
                v.emplace_back(el2);
            }
        }
        return List<U>{v};
    }
};

Note that we've only implemented unit and bind, getting fmap for free. Let's try it out:

List<int> list1{{1, 2, 3}};
const auto& list2 = list1.bind<int>([](int x) { return List{x + 1}; });
const auto& list3 = list1.fmap<int>([](int x) { return x + 2; });

The code was tested with GCC, MSVC, clang and ICC. It requires C++17.