Boost.Hana  1.0.2
Your standard library for metaprogramming

Description

The Monad concept represents Applicatives with the ability to flatten nested levels of structure.

Historically, Monads are a construction coming from category theory, an abstract branch of mathematics. The functional programming community eventually discovered how Monads could be used to formalize several useful things like side effects, which led to the wide adoption of Monads in that community. However, even in a multi-paradigm language like C++, there are several constructs which turn out to be Monads, like std::optional, std::vector and others.

Everybody tries to introduce Monads with a different analogy, and most people fail. This is called the Monad tutorial fallacy. We will try to avoid this trap by not presenting a specific intuition, and we will instead present what monads are mathematically. For specific intuitions, we will let readers who are new to this concept read one of the many excellent tutorials available online. Understanding Monads might take time at first, but once you get it, a lot of patterns will become obvious Monads; this enlightening will be your reward for the hard work.

There are different ways of defining a Monad; Haskell uses a function called bind (>>=) and another one called return (it has nothing to do with C++'s return statement). They then introduce relationships that must be satisfied for a type to be a Monad with those functions. Mathematicians sometimes use a function called join and another one called unit, or they also sometimes use other category theoretic constructions like functor adjunctions and the Kleisli category.

This library uses a composite approach. First, we use the flatten function (equivalent to join) along with the lift function from Applicative (equivalent to unit) to introduce the notion of monadic function composition. We then write the properties that must be satisfied by a Monad using this monadic composition operator, because we feel it shows the link between Monads and Monoids more clearly than other approaches.

Roughly speaking, we will say that a Monad is an Applicative which also defines a way to compose functions returning a monadic result, as opposed to only being able to compose functions returning a normal result. We will then ask for this composition to be associative and to have a neutral element, just like normal function composition. For usual composition, the neutral element is the identity function id. For monadic composition, the neutral element is the lift function defined by Applicative. This construction is made clearer in the laws below.

Note
Monads are known to be a big chunk to swallow. However, it is out of the scope of this documentation to provide a full-blown explanation of the concept. The Typeclassopedia is a nice Haskell-oriented resource where more information about Monads can be found.

Minimal complete definitions

First, a Monad must be both a Functor and an Applicative. Also, an implementation of flatten or chain satisfying the laws below for monadic composition must be provided.

Note
The ap method for Applicatives may be derived from the minimal complete definition of Monad and Functor; see below for more information.

Laws

To simplify writing the laws, we use the comparison between functions. For two functions f and g, we define

f == g if and only if f(x) == g(x) for all x

With the usual composition of functions, we are given two functions \( f : A \to B \) and \( g : B \to C \), and we must produce a new function \( compose(g, f) : A \to C \). This composition of functions is associative, which means that

compose(h, compose(g, f)) == compose(compose(h, g), f)

Also, this composition has an identity element, which is the identity function. This simply means that

compose(f, id) == compose(id, f) == f

This is probably nothing new if you are reading the Monad laws. Now, we can observe that the above is equivalent to saying that functions with the composition operator form a Monoid, where the neutral element is the identity function.

Given an Applicative F, what if we wanted to compose two functions \( f : A \to F(B) \) and \( g : B \to F(C) \)? When the Applicative F is also a Monad, such functions taking normal values but returning monadic values are called monadic functions. To compose them, we obviously can't use normal function composition, since the domains and codomains of f and g do not match properly. Instead, we'll need a new operator – let's call it monadic_compose:

\[ \mathtt{monadic\_compose} : (B \to F(C)) \times (A \to F(B)) \to (A \to F(C)) \]

How could we go about implementing this function? Well, since we know F is an Applicative, the only functions we have are transform (from Functor), and lift and ap (from Applicative). Hence, the only thing we can do at this point while respecting the signatures of f and g is to set (for x of type A)

monadic_compose(g, f)(x) = transform(f(x), g)

Indeed, f(x) is of type F(B), so we can map g (which takes B's) on it. Doing so will leave us with a result of type F(F(C)), but what we wanted was a result of type F(C) to respect the signature of monadic_compose. If we had a joker of type \( F(F(C)) \to F(C) \), we could simply set

monadic_compose(g, f)(x) = joker(transform(f(x), g))

and we would be happy. It turns out that flatten is precisely this joker. Now, we'll want our joker to satisfy some properties to make sure this composition is associative, just like our normal composition was. These properties are slightly cumbersome to specify, so we won't do it here. Also, we'll need some kind of neutral element for the composition. This neutral element can't be the usual identity function, because it does not have the right type: our neutral element needs to be a function of type \( X \to F(X) \) but the identity function has type \( X \to X \). It is now the right time to observe that lift from Applicative has exactly the right signature, and so we'll take this for our neutral element.

We are now ready to formulate the Monad laws using this composition operator. For a Monad M and functions \( f : A \to M(B) \), \( g : B \to M(C) \) and \( h : C \to M(D) \), the following must be satisfied:

// associativity
// right identity
monadic_compose(f, lift<M(A)>) == f
// left identity
monadic_compose(lift<M(B)>, f) == f

which is to say that M along with monadic composition is a Monoid where the neutral element is lift.

Refined concepts

  1. Functor
  2. Applicative (free implementation of ap)
    When the minimal complete definition for Monad and Functor are both satisfied, it is possible to implement ap by setting
    ap(fs, xs) = chain(fs, [](auto f) {
    return transform(xs, f);
    })

Concrete models

hana::lazy, hana::optional, hana::tuple

Variables

constexpr auto boost::hana::chain
 Feed a monadic value into a monadic computation.Given a monadic value and a monadic function, chain feeds the monadic value into the function, thus performing some Monad-specific effects, and returns the result. An implementation of chain must satisfy. More...
 
constexpr auto boost::hana::flatten
 Collapse two levels of monadic structure into a single level.Given a monadic value wrapped into two levels of monad, flatten removes one such level. An implementation of flatten must satisfy. More...
 
constexpr auto boost::hana::monadic_compose
 Composition of monadic functions.Given two monadic functions f and g, monadic_compose returns a new function equivalent to the composition of f with g, except the result of g is chained into f instead of simply passed to it, as with normal composition. monadic_compose satisfies. More...
 
template<typename M >
constexpr auto boost::hana::tap
 Tap inside a monadic chain.Given a function f, tap<M> returns a new function which performs f on its argument and then returns the argument lifted in the M Monad. Combined with the property that chain(m, lift<M>) == m, this provides a way of executing an action inside a monadic chain without influencing its overall result. This is useful to e.g. insert debug statements or perform actions that are not tied to the chain but that need to be executed inside of it. More...
 
constexpr auto boost::hana::then
 Sequentially compose two monadic actions, discarding any value produced by the first but not its effects. More...
 

Variable Documentation

constexpr auto boost::hana::chain

#include <boost/hana/fwd/chain.hpp>

Initial value:
= [](auto&& xs, auto&& f) -> decltype(auto) {
return tag-dispatched;
}

Feed a monadic value into a monadic computation.Given a monadic value and a monadic function, chain feeds the monadic value into the function, thus performing some Monad-specific effects, and returns the result. An implementation of chain must satisfy.

chain(xs, f) == flatten(transform(xs, f))

Signature

For a monad M, given a monadic value of type M(A) and a monadic function \( f : A \to M(B) \), chain has the signature \( \mathtt{chain} : M(A) \times (A \to M(B)) \to M(B) \).

Parameters
xsA monadic value to be fed to the function f.
fA function taking a normal value in the xs structure, and returning a monadic value. This function is called as f(x), where x is an element of the structure xs.

Example

// Copyright Louis Dionne 2013-2016
// Distributed under the Boost Software License, Version 1.0.
// (See accompanying file LICENSE.md or copy at http://boost.org/LICENSE_1_0.txt)
namespace hana = boost::hana;
BOOST_HANA_CONSTEXPR_LAMBDA auto deref = [](auto x) -> decltype(*x) {
return *x;
};
BOOST_HANA_CONSTEXPR_LAMBDA auto age = [](auto x) -> decltype(x.age) {
return x.age;
};
BOOST_HANA_CONSTEXPR_LAMBDA auto f = [](auto x) {
return hana::chain(hana::sfinae(deref)(x), hana::sfinae(age));
};
struct Person {
unsigned int age;
// ...
};
int main() {
Person john{30};
// Can't dereference a non-pointer.
BOOST_HANA_CONSTANT_CHECK(f(john) == hana::nothing);
// `int` has no member named `age`.
BOOST_HANA_CONSTANT_CHECK(f(1) == hana::nothing);
// All is good.
BOOST_HANA_CONSTEXPR_CHECK(f(&john) == hana::just(30u));
}
constexpr auto boost::hana::flatten

#include <boost/hana/fwd/flatten.hpp>

Initial value:
= [](auto&& xs) {
return tag-dispatched;
}

Collapse two levels of monadic structure into a single level.Given a monadic value wrapped into two levels of monad, flatten removes one such level. An implementation of flatten must satisfy.

flatten(xs) == chain(xs, id)

For Sequences, this simply takes a Sequence of Sequences, and returns a (non-recursively) flattened Sequence.

Signature

For a Monad M, the signature of flatten is \( \mathtt{flatten} : M(M(T)) \to M(T) \)

Parameters
xsA value with two levels of monadic structure, which should be collapsed into a single level of structure.

Example

// Copyright Louis Dionne 2013-2016
// Distributed under the Boost Software License, Version 1.0.
// (See accompanying file LICENSE.md or copy at http://boost.org/LICENSE_1_0.txt)
namespace hana = boost::hana;
static_assert(
hana::flatten(hana::make_tuple(hana::make_tuple(1, 2, 3),
hana::make_tuple(4, 5),
hana::make_tuple(6, 7, 8, 9)))
==
hana::make_tuple(1, 2, 3, 4, 5, 6, 7, 8, 9)
, "");
BOOST_HANA_CONSTANT_CHECK(hana::flatten(hana::nothing) == hana::nothing);
static_assert(hana::flatten(hana::just(hana::just(1))) == hana::just(1), "");
BOOST_HANA_CONSTANT_CHECK(hana::flatten(hana::just(hana::nothing)) == hana::nothing);
int main() { }
constexpr auto boost::hana::monadic_compose

#include <boost/hana/fwd/monadic_compose.hpp>

Initial value:
= [](auto&& f, auto&& g) {
return [perfect-capture](auto&& x) -> decltype(auto) {
return hana::chain(forwarded(g)(forwarded(x)), forwarded(f));
};
}
constexpr auto chain
Feed a monadic value into a monadic computation.Given a monadic value and a monadic function...
Definition: chain.hpp:51
constexpr auto capture
Create a function capturing the given variables.
Definition: capture.hpp:45

Composition of monadic functions.Given two monadic functions f and g, monadic_compose returns a new function equivalent to the composition of f with g, except the result of g is chained into f instead of simply passed to it, as with normal composition. monadic_compose satisfies.

monadic_compose(f, g)(x) == chain(g(x), f)
Note
Unlike compose, monadic_compose does not generalize nicely to arities higher than one. Hence, only unary functions may be used with monadic_compose.

Signature

Given a Monad M and two functions \( f : B \to M(C) \) and \( g : A \to M(B) \), the signature is \( \mathtt{monadic\_compose} : (B \to M(C)) \times (A \to M(B)) \to (A \to M(C)) \).

Parameters
fA monadic function with signature \( B \to M(C) \).
gA monadic function with signature \( A \to M(B) \).
Note
This method is not tag-dispatched, so it can't be customized directly.

Example

// Copyright Louis Dionne 2013-2016
// Distributed under the Boost Software License, Version 1.0.
// (See accompanying file LICENSE.md or copy at http://boost.org/LICENSE_1_0.txt)
namespace hana = boost::hana;
int main() {
BOOST_HANA_CONSTEXPR_LAMBDA auto block = [](auto ...types) {
return [=](auto x) {
return hana::if_(hana::contains(hana::make_tuple(types...), hana::typeid_(x)),
hana::nothing,
hana::just(x)
);
};
};
BOOST_HANA_CONSTEXPR_LAMBDA auto f = block(hana::type_c<double>);
BOOST_HANA_CONSTEXPR_LAMBDA auto g = block(hana::type_c<int>);
BOOST_HANA_CONSTEXPR_LAMBDA auto h = hana::monadic_compose(g, f);
BOOST_HANA_CONSTANT_CHECK(h(1) == hana::nothing); // fails inside g; 1 has type int
BOOST_HANA_CONSTANT_CHECK(h(1.2) == hana::nothing); // fails inside f; 1.2 has type double
BOOST_HANA_CONSTEXPR_CHECK(h('x') == hana::just('x')); // ok; 'x' has type char
}
template<typename M >
constexpr auto boost::hana::tap

#include <boost/hana/fwd/tap.hpp>

Initial value:
= [](auto&& f) {
return tag-dispatched;
}

Tap inside a monadic chain.Given a function f, tap<M> returns a new function which performs f on its argument and then returns the argument lifted in the M Monad. Combined with the property that chain(m, lift<M>) == m, this provides a way of executing an action inside a monadic chain without influencing its overall result. This is useful to e.g. insert debug statements or perform actions that are not tied to the chain but that need to be executed inside of it.

Note
Since C++ is not a pure language, it is possible to perform side effects inside the f function. Actually, side effects are the only reason why one might want to use tap. However, one should not rely on the side effects being done in any specific order.
Template Parameters
MThe tag (a Monad) of the monads in the tapped monadic chain.
Parameters
fA function to be executed inside a monadic chain. It will be called as f(x), where x is a value inside the previous monad in the chain. The result of f is always discarded.

Example

// Copyright Louis Dionne 2013-2016
// Distributed under the Boost Software License, Version 1.0.
// (See accompanying file LICENSE.md or copy at http://boost.org/LICENSE_1_0.txt)
#include <set>
namespace hana = boost::hana;
int main() {
// We use a sorted container because the order in which the functions
// are called is unspecified.
std::set<int> before, after;
auto xs = hana::make_tuple(1, 2, 3)
| hana::tap<hana::tuple_tag>([&](int x) { before.insert(x); })
| [](auto x) { return hana::make_tuple(x, -x); }
| hana::tap<hana::tuple_tag>([&](int x) { after.insert(x); });
BOOST_HANA_RUNTIME_CHECK(before == std::set<int>{1, 2, 3});
BOOST_HANA_RUNTIME_CHECK(after == std::set<int>{1, -1, 2, -2, 3, -3});
BOOST_HANA_RUNTIME_CHECK(xs == hana::make_tuple(1, -1, 2, -2, 3, -3));
}
constexpr auto boost::hana::then

#include <boost/hana/fwd/then.hpp>

Initial value:
= [](auto&& before, auto&& xs) -> decltype(auto) {
return tag-dispatched;
}

Sequentially compose two monadic actions, discarding any value produced by the first but not its effects.

Parameters
beforeThe first Monad in the monadic composition chain. The result of this monad is ignored, but its effects are combined with that of the second monad.
xsThe second Monad in the monadic composition chain.

Example

// Copyright Louis Dionne 2013-2016
// Distributed under the Boost Software License, Version 1.0.
// (See accompanying file LICENSE.md or copy at http://boost.org/LICENSE_1_0.txt)
namespace hana = boost::hana;
struct undefined { };
static_assert(
hana::then(hana::make_tuple(undefined{}, undefined{}), hana::make_tuple(1, 2, 3))
==
hana::make_tuple(
1, 2, 3,
1, 2, 3
)
, "");
int main() { }