Petr Homola
2 Feb 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.
Ground Floor, Verse Building, 18 Brunswick Place, London, N1 6DZ
108 E 16th Street, New York, NY 10003
Join over 111,000 others and get access to exclusive content, job opportunities and more!