fp_library/classes/monad_plus.rs
1//! Monads with a choice operator and identity element, combining [`Monad`](crate::classes::Monad) and [`Alternative`](crate::classes::Alternative).
2//!
3//! A `MonadPlus` is a type that supports both monadic sequencing
4//! ([`Monad`](crate::classes::Monad)) and choice with an identity element
5//! ([`Alternative`](crate::classes::Alternative)). It has no members of its own; it specifies that
6//! the type constructor has both `Monad` and `Alternative` instances.
7//!
8//! This module is a port of PureScript's
9//! [`Control.MonadPlus`](https://pursuit.purescript.org/packages/purescript-control/docs/Control.MonadPlus).
10//!
11//! # Hierarchy
12//!
13//! ```text
14//! Functor
15//! |
16//! +-- Pointed + Semiapplicative --> Applicative
17//! |
18//! +-- Applicative + Semimonad ----> Monad
19//! |
20//! +-- Alt + (identity element) ---> Plus
21//! |
22//! +-- Applicative + Plus ---------> Alternative
23//! |
24//! +-- Monad + Alternative --------> MonadPlus
25//! ```
26
27#[fp_macros::document_module(no_validation)]
28mod inner {
29 use crate::classes::*;
30
31 /// A type class for monads that also support choice, combining [`Monad`]
32 /// and [`Alternative`].
33 ///
34 /// `class (Monad m, Alternative m) => MonadPlus m`
35 ///
36 /// `MonadPlus` has no members of its own. It specifies that the type
37 /// constructor supports both monadic sequencing (`bind`, `pure`) and
38 /// choice with an identity element (`alt`, `empty`).
39 ///
40 /// # Laws
41 ///
42 /// A lawful `MonadPlus` must satisfy:
43 ///
44 /// - **Distributivity:** binding over a choice distributes:
45 ///
46 /// ```text
47 /// bind(alt(x, y), f) == alt(bind(x, f), bind(y, f))
48 /// ```
49 ///
50 /// The following property also holds for any `Monad + Alternative`:
51 ///
52 /// - **Left zero:** binding on the identity element yields the
53 /// identity element:
54 ///
55 /// ```text
56 /// bind(empty(), f) == empty()
57 /// ```
58 ///
59 /// # Examples
60 ///
61 /// Distributivity law for [`Vec`]:
62 ///
63 /// ```
64 /// use fp_library::{
65 /// brands::*,
66 /// functions::*,
67 /// };
68 ///
69 /// let x: Vec<i32> = vec![1, 2];
70 /// let y: Vec<i32> = vec![3, 4];
71 /// let f = |n: i32| vec![n * 10, n * 100];
72 ///
73 /// assert_eq!(
74 /// bind::<VecBrand, _, _>(alt::<VecBrand, _>(x.clone(), y.clone()), f),
75 /// alt::<VecBrand, _>(bind::<VecBrand, _, _>(x, f), bind::<VecBrand, _, _>(y, f)),
76 /// );
77 /// ```
78 ///
79 /// Left-zero law for [`Vec`]:
80 ///
81 /// ```
82 /// use fp_library::{
83 /// brands::*,
84 /// functions::*,
85 /// };
86 ///
87 /// let f = |n: i32| vec![n * 2];
88 ///
89 /// assert_eq!(
90 /// bind::<VecBrand, _, _>(plus_empty::<VecBrand, i32>(), f),
91 /// plus_empty::<VecBrand, i32>(),
92 /// );
93 /// ```
94 ///
95 /// # Implementors
96 ///
97 /// The blanket implementation applies to every brand with both [`Monad`]
98 /// and [`Alternative`]. The following brands are known to be *lawful*
99 /// (satisfying distributivity and left zero):
100 ///
101 /// - [`VecBrand`](crate::brands::VecBrand)
102 /// - [`CatListBrand`](crate::brands::CatListBrand)
103 ///
104 /// Note that [`OptionBrand`](crate::brands::OptionBrand) acquires the
105 /// trait via the blanket impl but does *not* satisfy the distributivity
106 /// law, because `alt` for `Option` picks the first `Some` and discards
107 /// the second branch entirely.
108 pub trait MonadPlus: Monad + Alternative {}
109
110 /// Blanket implementation of [`MonadPlus`].
111 #[document_type_parameters("The brand type.")]
112 impl<Brand> MonadPlus for Brand where Brand: Monad + Alternative {}
113}
114
115pub use inner::*;
116
117#[cfg(test)]
118mod tests {
119 use {
120 crate::{
121 brands::*,
122 functions::*,
123 types::cat_list::CatList,
124 },
125 quickcheck_macros::quickcheck,
126 };
127
128 // -- Distributivity: bind(alt(x, y), f) == alt(bind(x, f), bind(y, f)) --
129
130 /// Tests the distributivity law for MonadPlus with VecBrand.
131 #[quickcheck]
132 fn distributivity_vec(
133 x: Vec<i32>,
134 y: Vec<i32>,
135 ) -> bool {
136 let f = |n: i32| {
137 if n > 0 { vec![n.wrapping_mul(2)] } else { vec![] }
138 };
139 bind::<VecBrand, _, _>(alt::<VecBrand, _>(x.clone(), y.clone()), f)
140 == alt::<VecBrand, _>(bind::<VecBrand, _, _>(x, f), bind::<VecBrand, _, _>(y, f))
141 }
142
143 /// Tests the distributivity law for MonadPlus with CatListBrand.
144 #[quickcheck]
145 fn distributivity_cat_list(
146 xv: Vec<i32>,
147 yv: Vec<i32>,
148 ) -> bool {
149 let x: CatList<i32> = xv.into_iter().collect();
150 let y: CatList<i32> = yv.into_iter().collect();
151 let f = |n: i32| -> CatList<i32> {
152 if n > 0 { CatList::singleton(n.wrapping_mul(2)) } else { CatList::empty() }
153 };
154 bind::<CatListBrand, _, _>(alt::<CatListBrand, _>(x.clone(), y.clone()), f)
155 == alt::<CatListBrand, _>(
156 bind::<CatListBrand, _, _>(x, f),
157 bind::<CatListBrand, _, _>(y, f),
158 )
159 }
160
161 // -- Left zero: bind(empty(), f) == empty() --
162
163 /// Tests the left-zero law for MonadPlus with OptionBrand.
164 #[test]
165 fn left_zero_option() {
166 let f = |n: i32| if n > 0 { Some(n * 2) } else { None };
167 assert_eq!(
168 bind::<OptionBrand, _, _>(plus_empty::<OptionBrand, i32>(), f),
169 plus_empty::<OptionBrand, i32>(),
170 );
171 }
172
173 /// Tests the left-zero law for MonadPlus with VecBrand.
174 #[test]
175 fn left_zero_vec() {
176 let f = |n: i32| if n > 0 { vec![n * 2] } else { vec![] };
177 assert_eq!(
178 bind::<VecBrand, _, _>(plus_empty::<VecBrand, i32>(), f),
179 plus_empty::<VecBrand, i32>(),
180 );
181 }
182
183 /// Tests the left-zero law for MonadPlus with CatListBrand.
184 #[test]
185 fn left_zero_cat_list() {
186 let f = |n: i32| -> CatList<i32> {
187 if n > 0 { CatList::singleton(n * 2) } else { CatList::empty() }
188 };
189 assert_eq!(
190 bind::<CatListBrand, _, _>(plus_empty::<CatListBrand, i32>(), f),
191 plus_empty::<CatListBrand, i32>(),
192 );
193 }
194}