We're planting a tree for every job application! Click here to learn more
FunctionalWorks

Monads in C++ via static polymorphism

Petr Homola

2 Feb 2021

2 min read

Monads in C++ via static polymorphism
  • C++

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.

Did you like this article?

Petr Homola

BSc in physics, MSc in CS, PhD in computational linguistics

See other articles by Petr

Related jobs

Title

The company

title

Remote

Title

The company

title

Remote

Title

The company

title

Remote

Title

The company

title

Remote

Related articles

title

title

title

title

CareersCompaniesSitemapFunctional WorksBlockchain WorksJavaScript WorksAI WorksGolang WorksJava WorksPython WorksRemote Works
email iconhello@works-hub.comUK flag

Ground Floor, Verse Building, 18 Brunswick Place, London, N1 6DZ

US flag

108 E 16th Street, New York, NY 10003

Subscribe to our newsletter

Join over 111,000 others and get access to exclusive content, job opportunities and more!

© 2021 WorksHub

Privacy PolicyDeveloped by WorksHub