| 1 | /*! |
|---|
| 2 | @file |
|---|
| 3 | Forward declares `boost::hana::Monad`. |
|---|
| 4 | |
|---|
| 5 | Copyright Louis Dionne 2013-2022 |
|---|
| 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 | namespace boost { namespace hana { |
|---|
| 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 | }} // end namespace boost::hana |
|---|
| 197 | |
|---|
| 198 | #endif // !BOOST_HANA_FWD_CONCEPT_MONAD_HPP |
|---|
| 199 | |
|---|
