frunk/
monoid.rs

1//! Module for holding Monoid typeclass definitions and default implementations
2//!
3//! A `Monoid` is a Semigroup that has a defined empty/zero value. This allows us to
4//! define a `combine_all` method to work on a list of said things:
5#![cfg_attr(
6    feature = "std",
7    doc = r#"
8Have you ever wanted to combine 2 Hashmaps such that for a given key, if it exists in both maps,
9their values are summed in the new map?
10
11# Examples
12
13```
14# extern crate std;
15# use std::collections::HashMap;
16use frunk::{monoid, Monoid};
17
18let vec_of_no_hashmaps: Vec<HashMap<i32, String>> = Vec::new();
19assert_eq!(monoid::combine_all(&vec_of_no_hashmaps),
20           <HashMap<i32, String> as Monoid>::empty());
21
22let mut h1: HashMap<i32, String> = HashMap::new();
23h1.insert(1, String::from("Hello"));  // h1 is HashMap( 1 -> "Hello")
24let mut h2: HashMap<i32, String> = HashMap::new();
25h2.insert(1, String::from(" World"));
26h2.insert(2, String::from("Goodbye"));  // h2 is HashMap( 1 -> " World", 2 -> "Goodbye")
27let mut h3: HashMap<i32, String> = HashMap::new();
28h3.insert(3, String::from("Cruel World")); // h3 is HashMap( 3 -> "Cruel World")
29let vec_of_hashes = vec![h1, h2, h3];
30
31let mut h_expected: HashMap<i32, String> = HashMap::new();
32h_expected.insert(1, String::from("Hello World"));
33h_expected.insert(2, String::from("Goodbye"));
34h_expected.insert(3, String::from("Cruel World"));
35// h_expected is HashMap ( 1 -> "Hello World", 2 -> "Goodbye", 3 -> "Cruel World")
36assert_eq!(monoid::combine_all(&vec_of_hashes), h_expected);
37```"#
38)]
39
40use super::semigroup::{All, Any, Product, Semigroup};
41#[cfg(feature = "alloc")]
42use alloc::{string::String, vec::Vec};
43#[cfg(feature = "std")]
44use core::hash::Hash;
45#[cfg(feature = "std")]
46use std::collections::*;
47
48/// A Monoid is a Semigroup that has an empty/ zero value
49pub trait Monoid: Semigroup {
50    /// For a given Monoid, returns its empty/zero value
51    ///
52    /// # Examples
53    ///
54    /// ```
55    /// use frunk::Monoid;
56    ///
57    /// assert_eq!(<i16 as Monoid>::empty(), 0);
58    /// ```
59    fn empty() -> Self;
60}
61
62/// Return this combined with itself `n` times.
63///
64/// # Examples
65///
66/// ```
67/// use frunk::monoid;
68///
69/// assert_eq!(monoid::combine_n(&Some(2), 4), Some(8));
70/// ```
71pub fn combine_n<T>(o: &T, times: u32) -> T
72where
73    T: Monoid + Semigroup + Clone,
74{
75    if times == 0 {
76        <T as Monoid>::empty()
77    } else {
78        super::semigroup::combine_n(o, times)
79    }
80}
81
82/// Given a sequence of `xs`, combine them and return the total
83#[cfg_attr(
84    feature = "alloc",
85    doc = r#"
86# Examples
87
88```
89# extern crate alloc;
90# use alloc::vec::Vec;
91# use alloc::string::String;
92use frunk::monoid::combine_all;
93
94assert_eq!(combine_all(&vec![Some(1), Some(3)]), Some(4));
95
96let empty_vec_opt_int: Vec<Option<i32>> = Vec::new();
97assert_eq!(combine_all(&empty_vec_opt_int), None);
98
99let vec_of_some_strings = vec![Some(String::from("Hello")), Some(String::from(" World"))];
100assert_eq!(combine_all(&vec_of_some_strings), Some(String::from("Hello World")));
101```"#
102)]
103pub fn combine_all<T>(xs: &[T]) -> T
104where
105    T: Monoid + Semigroup + Clone,
106{
107    xs.iter()
108        .fold(<T as Monoid>::empty(), |acc, next| acc.combine(next))
109}
110
111impl<T> Monoid for Option<T>
112where
113    T: Semigroup + Clone,
114{
115    fn empty() -> Self {
116        None
117    }
118}
119
120#[cfg(feature = "alloc")]
121impl Monoid for String {
122    fn empty() -> Self {
123        String::new()
124    }
125}
126
127#[cfg(feature = "alloc")]
128impl<T> Monoid for Vec<T>
129where
130    T: Clone,
131{
132    fn empty() -> Self {
133        Vec::new()
134    }
135}
136
137#[cfg(feature = "std")]
138impl<T> Monoid for HashSet<T>
139where
140    T: Hash + Eq + Clone,
141{
142    fn empty() -> Self {
143        HashSet::new()
144    }
145}
146
147#[cfg(feature = "std")]
148impl<K, V> Monoid for HashMap<K, V>
149where
150    K: Eq + Hash + Clone,
151    V: Semigroup + Clone,
152{
153    fn empty() -> Self {
154        HashMap::new()
155    }
156}
157
158impl Monoid for All<bool> {
159    fn empty() -> Self {
160        All(true)
161    }
162}
163
164impl Monoid for Any<bool> {
165    fn empty() -> Self {
166        Any(false)
167    }
168}
169
170macro_rules! numeric_all_impls {
171    ($($tr:ty)*) => {
172      $(
173        impl Monoid for All<$tr> {
174            fn empty() -> Self { All(!0) }
175        }
176      )*
177    }
178}
179
180numeric_all_impls! { usize u8 u16 u32 u64 isize i8 i16 i32 i64 }
181
182macro_rules! numeric_any_impls {
183    ($($tr:ty)*) => {
184      $(
185        impl Monoid for Any<$tr> {
186            fn empty() -> Self { Any(0) }
187        }
188      )*
189    }
190}
191
192numeric_any_impls! { usize u8 u16 u32 u64 isize i8 i16 i32 i64 }
193
194macro_rules! numeric_monoid_imps {
195  ($($zero: expr; $tr:ty),*) => {
196    $(
197      impl Monoid for $tr {
198        fn empty() -> Self { $zero }
199      }
200    )*
201  }
202}
203
204numeric_monoid_imps! {
205    0; i8,
206    0; i16,
207    0; i32,
208    0; i64,
209    0; u8,
210    0; u16,
211    0; u32,
212    0; u64,
213    0; isize,
214    0; usize,
215    0f32; f32,
216    0f64; f64
217}
218
219macro_rules! numeric_product_monoid_imps {
220  ($($one: expr; $tr:ty),*) => {
221    $(
222      impl Monoid for Product<$tr> {
223        fn empty() -> Self { Product($one) }
224      }
225    )*
226  }
227}
228
229numeric_product_monoid_imps! {
230    1; i8,
231    1; i16,
232    1; i32,
233    1; i64,
234    1; u8,
235    1; u16,
236    1; u32,
237    1; u64,
238    1; isize,
239    1; usize,
240    1f32; f32,
241    1f64; f64
242}
243
244macro_rules! tuple_impls {
245    () => {}; // no more
246
247    (($idx:tt => $typ:ident), $( ($nidx:tt => $ntyp:ident), )*) => {
248// Invoke recursive reversal of list that ends in the macro expansion implementation
249// of the reversed list
250//
251        tuple_impls!([($idx, $typ);] $( ($nidx => $ntyp), )*);
252        tuple_impls!($( ($nidx => $ntyp), )*); // invoke macro on tail
253    };
254
255// ([accumulatedList], listToReverse); recursively calls tuple_impls until the list to reverse
256// + is empty (see next pattern)
257//
258    ([$(($accIdx: tt, $accTyp: ident);)+]  ($idx:tt => $typ:ident), $( ($nidx:tt => $ntyp:ident), )*) => {
259      tuple_impls!([($idx, $typ); $(($accIdx, $accTyp); )*] $( ($nidx => $ntyp), ) *);
260    };
261
262// Finally expand into our implementation
263    ([($idx:tt, $typ:ident); $( ($nidx:tt, $ntyp:ident); )*]) => {
264        impl<$typ: Monoid, $( $ntyp: Monoid),*> Monoid for ($typ, $( $ntyp ),*) {
265            fn empty() -> Self {
266              (<$typ as Monoid>::empty(), $(<$ntyp as Monoid>::empty(), )*)
267            }
268        }
269    }
270}
271
272tuple_impls! {
273    (20 => U),
274    (19 => T),
275    (18 => S),
276    (17 => R),
277    (16 => Q),
278    (15 => P),
279    (14 => O),
280    (13 => N),
281    (12 => M),
282    (11 => L),
283    (10 => K),
284    (9 => J),
285    (8 => I),
286    (7 => H),
287    (6 => G),
288    (5 => F),
289    (4 => E),
290    (3 => D),
291    (2 => C),
292    (1 => B),
293    (0 => A),
294}
295
296#[cfg(test)]
297mod tests {
298    use super::super::semigroup::{All, Any, Product};
299    use super::*;
300
301    #[cfg(feature = "alloc")]
302    use alloc::{borrow::ToOwned, vec};
303
304    #[test]
305    fn test_combine_n() {
306        assert_eq!(combine_n(&1, 0), 0);
307        assert_eq!(combine_n(&2, 1), 2);
308        assert_eq!(combine_n(&Some(2), 0), None);
309        assert_eq!(combine_n(&Some(2), 4), Some(8));
310    }
311
312    #[test]
313    #[cfg(feature = "alloc")]
314    fn test_combine_all_basic() {
315        assert_eq!(combine_all(&[1, 2, 3]), 6);
316        assert_eq!(combine_all(&[] as &[i32]), 0);
317        assert_eq!(combine_all(&[] as &[Option<i32>]), None);
318
319        let vec_of_some_strings = vec![Some("Hello".to_owned()), Some(" World".to_owned())];
320        assert_eq!(
321            combine_all(&vec_of_some_strings),
322            Some("Hello World".to_owned())
323        );
324    }
325
326    #[test]
327    #[cfg(feature = "std")]
328    fn test_combine_all_hashset() {
329        let vec_of_no_hashes: Vec<HashSet<i32>> = Vec::new();
330        assert_eq!(
331            combine_all(&vec_of_no_hashes),
332            <HashSet<i32> as Monoid>::empty()
333        );
334
335        let mut h1 = HashSet::new();
336        h1.insert(1);
337        let mut h2 = HashSet::new();
338        h2.insert(2);
339        let mut h3 = HashSet::new();
340        h3.insert(3);
341        let vec_of_hashes = vec![h1, h2, h3];
342        let mut h_expected = HashSet::new();
343        h_expected.insert(1);
344        h_expected.insert(2);
345        h_expected.insert(3);
346        assert_eq!(combine_all(&vec_of_hashes), h_expected);
347    }
348
349    #[test]
350    #[cfg(feature = "std")]
351    fn test_combine_all_hashmap() {
352        let vec_of_no_hashmaps: Vec<HashMap<i32, String>> = Vec::new();
353        assert_eq!(
354            combine_all(&vec_of_no_hashmaps),
355            <HashMap<i32, String> as Monoid>::empty()
356        );
357
358        let mut h1: HashMap<i32, String> = HashMap::new();
359        h1.insert(1, String::from("Hello")); // h1 is HashMap( 1 -> "Hello")
360        let mut h2: HashMap<i32, String> = HashMap::new();
361        h2.insert(1, String::from(" World"));
362        h2.insert(2, String::from("Goodbye")); // h2 is HashMap( 1 -> " World", 2 -> "Goodbye")
363        let mut h3: HashMap<i32, String> = HashMap::new();
364        h3.insert(3, String::from("Cruel World")); // h3 is HashMap( 3 -> "Cruel World")
365        let vec_of_hashes = vec![h1, h2, h3];
366
367        let mut h_expected: HashMap<i32, String> = HashMap::new();
368        h_expected.insert(1, String::from("Hello World"));
369        h_expected.insert(2, String::from("Goodbye"));
370        h_expected.insert(3, String::from("Cruel World")); // h_expected is HashMap ( 1 -> "Hello World", 2 -> "Goodbye", 3 -> "Cruel World")
371        assert_eq!(combine_all(&vec_of_hashes), h_expected);
372    }
373
374    #[test]
375    fn test_combine_all_all() {
376        assert_eq!(combine_all(&[] as &[All<i32>]), All(!0));
377        assert_eq!(combine_all(&[All(3), All(7)]), All(3));
378
379        assert_eq!(combine_all(&[] as &[All<bool>]), All(true));
380        assert_eq!(combine_all(&[All(false), All(false)]), All(false));
381        assert_eq!(combine_all(&[All(true), All(true)]), All(true));
382    }
383
384    #[test]
385    fn test_combine_all_any() {
386        assert_eq!(combine_all(&[] as &[Any<i32>]), Any(0));
387        assert_eq!(combine_all(&[Any(3), Any(8)]), Any(11));
388
389        assert_eq!(combine_all(&[] as &[Any<bool>]), Any(false));
390        assert_eq!(combine_all(&[Any(false), Any(false)]), Any(false));
391        assert_eq!(combine_all(&[Any(true), Any(false)]), Any(true));
392    }
393
394    #[test]
395    #[cfg(feature = "alloc")]
396    fn test_combine_all_tuple() {
397        let t1 = (1, 2.5f32, String::from("hi"), Some(3));
398        let t2 = (1, 2.5f32, String::from(" world"), None);
399        let t3 = (1, 2.5f32, String::from(", goodbye"), Some(10));
400        let tuples = vec![t1, t2, t3];
401
402        let expected = (3, 7.5f32, String::from("hi world, goodbye"), Some(13));
403        assert_eq!(combine_all(&tuples), expected)
404    }
405
406    #[test]
407    fn test_combine_all_product() {
408        let v = [Product(2), Product(3), Product(4)];
409        assert_eq!(combine_all(&v), Product(24))
410    }
411}
frunk/monoid.rs

frunk/
monoid.rs
