1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
|
/*!
@file
Forward declares `boost::hana::Monad`.
@copyright Louis Dionne 2013-2017
Distributed under the Boost Software License, Version 1.0.
(See accompanying file LICENSE.md or copy at http://boost.org/LICENSE_1_0.txt)
*/
#ifndef BOOST_HANA_FWD_CONCEPT_MONAD_HPP
#define BOOST_HANA_FWD_CONCEPT_MONAD_HPP
#include <boost/hana/config.hpp>
BOOST_HANA_NAMESPACE_BEGIN
//! @ingroup group-concepts
//! @defgroup group-Monad Monad
//! The `Monad` concept represents `Applicative`s 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 `Monad`s with a different analogy, and
//! most people fail. This is called the [Monad tutorial fallacy][1]. 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][2] 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
//! @code
//! f == g if and only if f(x) == g(x) for all x
//! @endcode
//!
//! With the usual composition of functions, we are given two functions
//! @f$ f : A \to B @f$ and @f$ g : B \to C @f$, and we must produce a
//! new function @f$ compose(g, f) : A \to C @f$. This composition of
//! functions is associative, which means that
//! @code
//! compose(h, compose(g, f)) == compose(compose(h, g), f)
//! @endcode
//!
//! Also, this composition has an identity element, which is the identity
//! function. This simply means that
//! @code
//! compose(f, id) == compose(id, f) == f
//! @endcode
//!
//! 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$ f : A \to F(B) @f$ and @f$ g : B \to F(C) @f$? 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`:
//! @f[
//! \mathtt{monadic\_compose} :
//! (B \to F(C)) \times (A \to F(B)) \to (A \to F(C))
//! @f]
//!
//! 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`)
//! @code
//! monadic_compose(g, f)(x) = transform(f(x), g)
//! @endcode
//!
//! 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(F(C)) \to F(C) @f$,
//! we could simply set
//! @code
//! monadic_compose(g, f)(x) = joker(transform(f(x), g))
//! @endcode
//!
//! 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 @f$ X \to F(X) @f$ but the identity function has
//! type @f$ X \to X @f$. 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$ f : A \to M(B) @f$,
//! @f$ g : B \to M(C) @f$ and @f$ h : C \to M(D) @f$, the following
//! must be satisfied:
//! @code
//! // associativity
//! monadic_compose(h, monadic_compose(g, f)) == monadic_compose(monadic_compose(h, g), f)
//!
//! // right identity
//! monadic_compose(f, lift<M(A)>) == f
//!
//! // left identity
//! monadic_compose(lift<M(B)>, f) == f
//! @endcode
//!
//! 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`)\n
//! When the minimal complete definition for `Monad` and `Functor` are
//! both satisfied, it is possible to implement `ap` by setting
//! @code
//! ap(fs, xs) = chain(fs, [](auto f) {
//! return transform(xs, f);
//! })
//! @endcode
//!
//!
//! Concrete models
//! ---------------
//! `hana::lazy`, `hana::optional`, `hana::tuple`
//!
//!
//! [1]: https://byorgey.wordpress.com/2009/01/12/abstraction-intuition-and-the-monad-tutorial-fallacy/
//! [2]: https://wiki.haskell.org/Typeclassopedia#Monad
template <typename M>
struct Monad;
BOOST_HANA_NAMESPACE_END
#endif // !BOOST_HANA_FWD_CONCEPT_MONAD_HPP
|
