]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
1 | /*! |
2 | @file | |
3 | Forward declares `boost::hana::Monad`. | |
4 | ||
5 | @copyright Louis Dionne 2013-2016 | |
6 | Distributed under the Boost Software License, Version 1.0. | |
7 | (See accompanying file LICENSE.md or copy at http://boost.org/LICENSE_1_0.txt) | |
8 | */ | |
9 | ||
10 | #ifndef BOOST_HANA_FWD_CONCEPT_MONAD_HPP | |
11 | #define BOOST_HANA_FWD_CONCEPT_MONAD_HPP | |
12 | ||
13 | #include <boost/hana/config.hpp> | |
14 | ||
15 | ||
16 | BOOST_HANA_NAMESPACE_BEGIN | |
17 | //! @ingroup group-concepts | |
18 | //! @defgroup group-Monad Monad | |
19 | //! The `Monad` concept represents `Applicative`s with the ability to | |
20 | //! flatten nested levels of structure. | |
21 | //! | |
22 | //! Historically, Monads are a construction coming from category theory, | |
23 | //! an abstract branch of mathematics. The functional programming | |
24 | //! community eventually discovered how Monads could be used to | |
25 | //! formalize several useful things like side effects, which led | |
26 | //! to the wide adoption of Monads in that community. However, even | |
27 | //! in a multi-paradigm language like C++, there are several constructs | |
28 | //! which turn out to be Monads, like `std::optional`, `std::vector` and | |
29 | //! others. | |
30 | //! | |
31 | //! Everybody tries to introduce `Monad`s with a different analogy, and | |
32 | //! most people fail. This is called the [Monad tutorial fallacy][1]. We | |
33 | //! will try to avoid this trap by not presenting a specific intuition, | |
34 | //! and we will instead present what monads are mathematically. | |
35 | //! For specific intuitions, we will let readers who are new to this | |
36 | //! concept read one of the many excellent tutorials available online. | |
37 | //! Understanding Monads might take time at first, but once you get it, | |
38 | //! a lot of patterns will become obvious Monads; this enlightening will | |
39 | //! be your reward for the hard work. | |
40 | //! | |
41 | //! There are different ways of defining a Monad; Haskell uses a function | |
42 | //! called `bind` (`>>=`) and another one called `return` (it has nothing | |
43 | //! to do with C++'s `return` statement). They then introduce relationships | |
44 | //! that must be satisfied for a type to be a Monad with those functions. | |
45 | //! Mathematicians sometimes use a function called `join` and another one | |
46 | //! called `unit`, or they also sometimes use other category theoretic | |
47 | //! constructions like functor adjunctions and the Kleisli category. | |
48 | //! | |
49 | //! This library uses a composite approach. First, we use the `flatten` | |
50 | //! function (equivalent to `join`) along with the `lift` function from | |
51 | //! `Applicative` (equivalent to `unit`) to introduce the notion of | |
52 | //! monadic function composition. We then write the properties that must | |
53 | //! be satisfied by a Monad using this monadic composition operator, | |
54 | //! because we feel it shows the link between Monads and Monoids more | |
55 | //! clearly than other approaches. | |
56 | //! | |
57 | //! Roughly speaking, we will say that a `Monad` is an `Applicative` which | |
58 | //! also defines a way to compose functions returning a monadic result, | |
59 | //! as opposed to only being able to compose functions returning a normal | |
60 | //! result. We will then ask for this composition to be associative and to | |
61 | //! have a neutral element, just like normal function composition. For | |
62 | //! usual composition, the neutral element is the identity function `id`. | |
63 | //! For monadic composition, the neutral element is the `lift` function | |
64 | //! defined by `Applicative`. This construction is made clearer in the | |
65 | //! laws below. | |
66 | //! | |
67 | //! @note | |
68 | //! Monads are known to be a big chunk to swallow. However, it is out of | |
69 | //! the scope of this documentation to provide a full-blown explanation | |
70 | //! of the concept. The [Typeclassopedia][2] is a nice Haskell-oriented | |
71 | //! resource where more information about Monads can be found. | |
72 | //! | |
73 | //! | |
74 | //! Minimal complete definitions | |
75 | //! ---------------------------- | |
76 | //! First, a `Monad` must be both a `Functor` and an `Applicative`. | |
77 | //! Also, an implementation of `flatten` or `chain` satisfying the | |
78 | //! laws below for monadic composition must be provided. | |
79 | //! | |
80 | //! @note | |
81 | //! The `ap` method for `Applicatives` may be derived from the minimal | |
82 | //! complete definition of `Monad` and `Functor`; see below for more | |
83 | //! information. | |
84 | //! | |
85 | //! | |
86 | //! Laws | |
87 | //! ---- | |
88 | //! To simplify writing the laws, we use the comparison between functions. | |
89 | //! For two functions `f` and `g`, we define | |
90 | //! @code | |
91 | //! f == g if and only if f(x) == g(x) for all x | |
92 | //! @endcode | |
93 | //! | |
94 | //! With the usual composition of functions, we are given two functions | |
95 | //! @f$ f : A \to B @f$ and @f$ g : B \to C @f$, and we must produce a | |
96 | //! new function @f$ compose(g, f) : A \to C @f$. This composition of | |
97 | //! functions is associative, which means that | |
98 | //! @code | |
99 | //! compose(h, compose(g, f)) == compose(compose(h, g), f) | |
100 | //! @endcode | |
101 | //! | |
102 | //! Also, this composition has an identity element, which is the identity | |
103 | //! function. This simply means that | |
104 | //! @code | |
105 | //! compose(f, id) == compose(id, f) == f | |
106 | //! @endcode | |
107 | //! | |
108 | //! This is probably nothing new if you are reading the `Monad` laws. | |
109 | //! Now, we can observe that the above is equivalent to saying that | |
110 | //! functions with the composition operator form a `Monoid`, where the | |
111 | //! neutral element is the identity function. | |
112 | //! | |
113 | //! Given an `Applicative` `F`, what if we wanted to compose two functions | |
114 | //! @f$ f : A \to F(B) @f$ and @f$ g : B \to F(C) @f$? When the | |
115 | //! `Applicative` `F` is also a `Monad`, such functions taking normal | |
116 | //! values but returning monadic values are called _monadic functions_. | |
117 | //! To compose them, we obviously can't use normal function composition, | |
118 | //! since the domains and codomains of `f` and `g` do not match properly. | |
119 | //! Instead, we'll need a new operator -- let's call it `monadic_compose`: | |
120 | //! @f[ | |
121 | //! \mathtt{monadic\_compose} : | |
122 | //! (B \to F(C)) \times (A \to F(B)) \to (A \to F(C)) | |
123 | //! @f] | |
124 | //! | |
125 | //! How could we go about implementing this function? Well, since we know | |
126 | //! `F` is an `Applicative`, the only functions we have are `transform` | |
127 | //! (from `Functor`), and `lift` and `ap` (from `Applicative`). Hence, | |
128 | //! the only thing we can do at this point while respecting the signatures | |
129 | //! of `f` and `g` is to set (for `x` of type `A`) | |
130 | //! @code | |
131 | //! monadic_compose(g, f)(x) = transform(f(x), g) | |
132 | //! @endcode | |
133 | //! | |
134 | //! Indeed, `f(x)` is of type `F(B)`, so we can map `g` (which takes `B`'s) | |
135 | //! on it. Doing so will leave us with a result of type `F(F(C))`, but what | |
136 | //! we wanted was a result of type `F(C)` to respect the signature of | |
137 | //! `monadic_compose`. If we had a joker of type @f$ F(F(C)) \to F(C) @f$, | |
138 | //! we could simply set | |
139 | //! @code | |
140 | //! monadic_compose(g, f)(x) = joker(transform(f(x), g)) | |
141 | //! @endcode | |
142 | //! | |
143 | //! and we would be happy. It turns out that `flatten` is precisely this | |
144 | //! joker. Now, we'll want our joker to satisfy some properties to make | |
145 | //! sure this composition is associative, just like our normal composition | |
146 | //! was. These properties are slightly cumbersome to specify, so we won't | |
147 | //! do it here. Also, we'll need some kind of neutral element for the | |
148 | //! composition. This neutral element can't be the usual identity function, | |
149 | //! because it does not have the right type: our neutral element needs to | |
150 | //! be a function of type @f$ X \to F(X) @f$ but the identity function has | |
151 | //! type @f$ X \to X @f$. It is now the right time to observe that `lift` | |
152 | //! from `Applicative` has exactly the right signature, and so we'll take | |
153 | //! this for our neutral element. | |
154 | //! | |
155 | //! We are now ready to formulate the `Monad` laws using this composition | |
156 | //! operator. For a `Monad` `M` and functions @f$ f : A \to M(B) @f$, | |
157 | //! @f$ g : B \to M(C) @f$ and @f$ h : C \to M(D) @f$, the following | |
158 | //! must be satisfied: | |
159 | //! @code | |
160 | //! // associativity | |
161 | //! monadic_compose(h, monadic_compose(g, f)) == monadic_compose(monadic_compose(h, g), f) | |
162 | //! | |
163 | //! // right identity | |
164 | //! monadic_compose(f, lift<M(A)>) == f | |
165 | //! | |
166 | //! // left identity | |
167 | //! monadic_compose(lift<M(B)>, f) == f | |
168 | //! @endcode | |
169 | //! | |
170 | //! which is to say that `M` along with monadic composition is a Monoid | |
171 | //! where the neutral element is `lift`. | |
172 | //! | |
173 | //! | |
174 | //! Refined concepts | |
175 | //! ---------------- | |
176 | //! 1. `Functor` | |
177 | //! 2. `Applicative` (free implementation of `ap`)\n | |
178 | //! When the minimal complete definition for `Monad` and `Functor` are | |
179 | //! both satisfied, it is possible to implement `ap` by setting | |
180 | //! @code | |
181 | //! ap(fs, xs) = chain(fs, [](auto f) { | |
182 | //! return transform(xs, f); | |
183 | //! }) | |
184 | //! @endcode | |
185 | //! | |
186 | //! | |
187 | //! Concrete models | |
188 | //! --------------- | |
189 | //! `hana::lazy`, `hana::optional`, `hana::tuple` | |
190 | //! | |
191 | //! | |
192 | //! [1]: https://byorgey.wordpress.com/2009/01/12/abstraction-intuition-and-the-monad-tutorial-fallacy/ | |
193 | //! [2]: https://wiki.haskell.org/Typeclassopedia#Monad | |
194 | template <typename M> | |
195 | struct Monad; | |
196 | BOOST_HANA_NAMESPACE_END | |
197 | ||
198 | #endif // !BOOST_HANA_FWD_CONCEPT_MONAD_HPP |