We use cookies and other tracking technologies to improve your browsing experience on our site, analyze site traffic, and understand where our audience is coming from. To find out more, please read our privacy policy.

By choosing 'I Accept', you consent to our use of cookies and other tracking technologies.

We use cookies and other tracking technologies to improve your browsing experience on our site, analyze site traffic, and understand where our audience is coming from. To find out more, please read our privacy policy.

By choosing 'I Accept', you consent to our use of cookies and other tracking technologies. Less

We use cookies and other tracking technologies... More

Login or register
to apply for this job!

Login or register
to save this job!

Login or register
to save interesting jobs!

Login or register
to get access to all your job applications!

Login or register to start contributing with an article!

Login or register
to see more jobs from this company!

Login or register
to boost this post!

Show some love to the author of this blog by giving their post some rocket fuel 🚀.

Login or register to search for your ideal job!

Login or register to start working on this issue!

Engineers who find a new job through Functional Works average a 15% increase in salary 🚀

Blog hero image

Monads in C++ via static polymorphism

Petr Homola 1 January, 2021 | 2 min read

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.

Author's avatar
Petr Homola
BSc in physics, PhD in computer science, researcher on artificial intelligence, living in Baile Átha Cliath, Éire
    C++
    Swift
    Go
    Java
    C#
    flutter

Related Issues

cosmos / gaia
  • Open
  • 0
  • 0
  • Intermediate
  • Go
cosmos / gaia
  • Open
  • 0
  • 0
  • Intermediate
  • Go
cosmos / ibc
  • Open
  • 0
  • 0
  • Intermediate
  • TeX
cosmos / ibc
cosmos / ibc
  • Open
  • 0
  • 0
  • Intermediate
  • TeX
WorksHub / client
  • Started
  • 0
  • 28
  • Intermediate
  • Clojure
  • $150
viebel / klipse-clj
viebel / klipse-clj
  • Started
  • 0
  • 4
  • Intermediate
  • Clojure
viebel / klipse
  • Started
  • 0
  • 1
  • Intermediate
  • Clojure
viebel / klipse
  • 1
  • 0
  • Intermediate
  • Clojure

Get hired!

Sign up now and apply for roles at companies that interest you.

Engineers who find a new job through Functional Works average a 15% increase in salary.

Start with GitHubStart with Stack OverflowStart with Email