frunk/
semigroup.rs

1//! Module for holding the Semigroup typeclass definition and typeclass instances
2//!
3//! You can, for example, combine tuples.
4#![cfg_attr(
5    feature = "alloc",
6    doc = r#"
7# Examples
8
9```
10# fn main() {
11use frunk::Semigroup;
12use frunk_core::hlist;
13
14let t1 = (1, 2.5f32, String::from("hi"), Some(3));
15let t2 = (1, 2.5f32, String::from(" world"), None);
16
17let expected = (2, 5.0f32, String::from("hi world"), Some(3));
18
19assert_eq!(t1.combine(&t2), expected);
20
21// ultimately, the Tuple-based Semigroup implementations are only available for a maximum of
22// 26 elements. If you need more, use HList, which is has no such limit.
23
24let h1 = hlist![1, 3.3, 53i64];
25let h2 = hlist![2, 1.2, 1i64];
26let h3 = hlist![3, 4.5, 54];
27assert_eq!(h1.combine(&h2), h3)
28# }
29```"#
30)]
31
32#[cfg(feature = "alloc")]
33use alloc::{boxed::Box, string::String, vec::Vec};
34use core::cell::*;
35use core::cmp::Ordering;
36#[cfg(feature = "alloc")]
37use core::hash::Hash;
38use core::ops::{BitAnd, BitOr, Deref};
39use frunk_core::hlist::*;
40#[cfg(feature = "std")]
41use std::collections::hash_map::Entry;
42#[cfg(feature = "std")]
43use std::collections::{HashMap, HashSet};
44
45/// Wrapper type for types that are ordered and can have a Max combination
46#[derive(PartialEq, Debug, Eq, Clone, Copy, PartialOrd, Ord, Hash)]
47pub struct Max<T: Ord>(pub T);
48
49/// Wrapper type for types that are ordered and can have a Min combination
50#[derive(PartialEq, Debug, Eq, Clone, Copy, PartialOrd, Ord, Hash)]
51pub struct Min<T: Ord>(pub T);
52
53/// Wrapper type for types that can have a Product combination
54#[derive(PartialEq, Debug, Eq, Clone, Copy, PartialOrd, Ord, Hash)]
55pub struct Product<T>(pub T);
56
57/// Wrapper type for boolean that acts as a bitwise && combination
58#[derive(PartialEq, Debug, Eq, Clone, Copy, PartialOrd, Ord, Hash)]
59pub struct All<T>(pub T);
60
61/// Wrapper type for boolean that acts as a bitwise || combination
62#[derive(PartialEq, Debug, Eq, Clone, Copy, PartialOrd, Ord, Hash)]
63pub struct Any<T>(pub T);
64
65/// A Semigroup is a class of thing that has a definable combine operation
66pub trait Semigroup {
67    /// Associative operation taking which combines two values.
68    ///
69    /// # Examples
70    ///
71    /// ```
72    /// use frunk::Semigroup;
73    ///
74    /// assert_eq!(Some(1).combine(&Some(2)), Some(3))
75    /// ```
76    fn combine(&self, other: &Self) -> Self;
77}
78
79/// Allow the combination of any two HLists having the same structure
80/// if all of the sub-element types are also Semiups
81impl<H: Semigroup, T: HList + Semigroup> Semigroup for HCons<H, T> {
82    fn combine(&self, other: &Self) -> Self {
83        self.tail
84            .combine(&other.tail)
85            .prepend(self.head.combine(&other.head))
86    }
87}
88
89/// Since () + () = (), the same is true for HNil
90impl Semigroup for HNil {
91    fn combine(&self, _: &Self) -> Self {
92        *self
93    }
94}
95
96/// Return this combined with itself `n` times.
97pub fn combine_n<T>(o: &T, times: u32) -> T
98where
99    T: Semigroup + Clone,
100{
101    let mut x = o.clone();
102    // note: range is non-inclusive in the upper bound
103    for _ in 1..times {
104        x = o.combine(&x);
105    }
106    x
107}
108
109/// Given a sequence of `xs`, combine them and return the total
110///
111/// If the sequence is empty, returns None. Otherwise, returns Some(total).
112///
113/// # Examples
114///
115/// ```
116/// use frunk::semigroup::combine_all_option;
117///
118/// let v1 = &vec![1, 2, 3];
119/// assert_eq!(combine_all_option(v1), Some(6));
120///
121/// let v2: Vec<i16> = Vec::new(); // empty!
122/// assert_eq!(combine_all_option(&v2), None);
123/// ```
124pub fn combine_all_option<T>(xs: &[T]) -> Option<T>
125where
126    T: Semigroup + Clone,
127{
128    xs.first()
129        .map(|head| xs[1..].iter().fold(head.clone(), |a, b| a.combine(b)))
130}
131
132macro_rules! numeric_semigroup_imps {
133  ($($tr:ty),*) => {
134    $(
135      impl Semigroup for $tr {
136        fn combine(&self, other: &Self) -> Self { self + other }
137      }
138    )*
139  }
140}
141
142numeric_semigroup_imps!(i8, i16, i32, i64, u8, u16, u32, u64, isize, usize, f32, f64);
143
144macro_rules! numeric_product_semigroup_imps {
145  ($($tr:ty),*) => {
146    $(
147      impl Semigroup for Product<$tr> {
148        fn combine(&self, other: &Self) -> Self {
149            let Product(x) = *self;
150            let Product(y) = *other;
151            Product(x * y)
152         }
153      }
154    )*
155  }
156}
157
158numeric_product_semigroup_imps!(i8, i16, i32, i64, u8, u16, u32, u64, isize, usize, f32, f64);
159
160impl<T> Semigroup for Option<T>
161where
162    T: Semigroup + Clone,
163{
164    fn combine(&self, other: &Self) -> Self {
165        match (self, other) {
166            (Some(ref v), Some(ref v_other)) => Some(v.combine(v_other)),
167            (Some(_), _) => self.clone(),
168            _ => other.clone(),
169        }
170    }
171}
172
173#[cfg(feature = "alloc")]
174impl<T: Semigroup> Semigroup for Box<T> {
175    fn combine(&self, other: &Self) -> Self {
176        Box::new(self.deref().combine(other.deref()))
177    }
178}
179
180#[cfg(feature = "alloc")]
181impl Semigroup for String {
182    fn combine(&self, other: &Self) -> Self {
183        let mut cloned = self.clone();
184        cloned.push_str(other);
185        cloned
186    }
187}
188
189#[cfg(feature = "alloc")]
190impl<T: Clone> Semigroup for Vec<T> {
191    fn combine(&self, other: &Self) -> Self {
192        let mut v = self.clone();
193        v.extend_from_slice(other);
194        v
195    }
196}
197
198impl<T> Semigroup for Cell<T>
199where
200    T: Semigroup + Copy,
201{
202    fn combine(&self, other: &Self) -> Self {
203        Cell::new(self.get().combine(&(other.get())))
204    }
205}
206
207impl<T: Semigroup> Semigroup for RefCell<T> {
208    fn combine(&self, other: &Self) -> Self {
209        let self_b = self.borrow();
210        let other_b = other.borrow();
211        RefCell::new(self_b.deref().combine(other_b.deref()))
212    }
213}
214
215#[cfg(feature = "std")]
216impl<T> Semigroup for HashSet<T>
217where
218    T: Eq + Hash + Clone,
219{
220    fn combine(&self, other: &Self) -> Self {
221        self.union(other).cloned().collect()
222    }
223}
224
225#[cfg(feature = "std")]
226impl<K, V> Semigroup for HashMap<K, V>
227where
228    K: Eq + Hash + Clone,
229    V: Semigroup + Clone,
230{
231    fn combine(&self, other: &Self) -> Self {
232        let mut h: HashMap<K, V> = self.clone();
233        for (k, v) in other {
234            let k_clone = k.clone();
235            match h.entry(k_clone) {
236                Entry::Occupied(o) => {
237                    let existing = o.into_mut();
238                    let comb = existing.combine(v);
239                    *existing = comb;
240                }
241                Entry::Vacant(o) => {
242                    o.insert(v.clone());
243                }
244            }
245        }
246        h
247    }
248}
249
250impl<T> Semigroup for Max<T>
251where
252    T: Ord + Clone,
253{
254    fn combine(&self, other: &Self) -> Self {
255        let x = self.0.clone();
256        let y = other.0.clone();
257        match x.cmp(&y) {
258            Ordering::Less => Max(y),
259            _ => Max(x),
260        }
261    }
262}
263
264impl<T> Semigroup for Min<T>
265where
266    T: Ord + Clone,
267{
268    fn combine(&self, other: &Self) -> Self {
269        let x = self.0.clone();
270        let y = other.0.clone();
271        match x.cmp(&y) {
272            Ordering::Less => Min(x),
273            _ => Min(y),
274        }
275    }
276}
277
278// Deriving for all BitAnds sucks because we are then bound on ::Output, which may not be the same type
279macro_rules! simple_all_impls {
280    ($($tr:ty)*) => {
281        $(
282            impl Semigroup for All<$tr> {
283                fn combine(&self, other: &Self) -> Self {
284                    let x = self.0;
285                    let y = other.0;
286                    All(x.bitand(y))
287                }
288            }
289        )*
290    }
291}
292
293simple_all_impls! { bool usize u8 u16 u32 u64 isize i8 i16 i32 i64 }
294
295macro_rules! simple_any_impls {
296    ($($tr:ty)*) => {
297        $(
298            impl Semigroup for Any<$tr> {
299                fn combine(&self, other: &Self) -> Self {
300                    let x = self.0;
301                    let y = other.0;
302                    Any(x.bitor(y))
303                }
304            }
305        )*
306    }
307}
308
309simple_any_impls! { bool usize u8 u16 u32 u64 isize i8 i16 i32 i64 }
310
311macro_rules! tuple_impls {
312    () => {}; // no more
313
314    (($idx:tt => $typ:ident), $( ($nidx:tt => $ntyp:ident), )*) => {
315// Invoke recursive reversal of list that ends in the macro expansion implementation
316// of the reversed list
317//
318        tuple_impls!([($idx, $typ);] $( ($nidx => $ntyp), )*);
319        tuple_impls!($( ($nidx => $ntyp), )*); // invoke macro on tail
320    };
321
322// ([accumulatedList], listToReverse); recursively calls tuple_impls until the list to reverse
323// + is empty (see next pattern)
324//
325    ([$(($accIdx: tt, $accTyp: ident);)+]  ($idx:tt => $typ:ident), $( ($nidx:tt => $ntyp:ident), )*) => {
326      tuple_impls!([($idx, $typ); $(($accIdx, $accTyp); )*] $( ($nidx => $ntyp), ) *);
327    };
328
329// Finally expand into our implementation
330    ([($idx:tt, $typ:ident); $( ($nidx:tt, $ntyp:ident); )*]) => {
331        impl<$typ: Semigroup, $( $ntyp: Semigroup),*> Semigroup for ($typ, $( $ntyp ),*) {
332            fn combine(&self, other: &Self) -> Self {
333                (self.$idx.combine(&other.$idx), $(self.$nidx.combine(&other.$nidx), )*)
334            }
335        }
336    }
337}
338
339tuple_impls! {
340    (20 => U),
341    (19 => T),
342    (18 => S),
343    (17 => R),
344    (16 => Q),
345    (15 => P),
346    (14 => O),
347    (13 => N),
348    (12 => M),
349    (11 => L),
350    (10 => K),
351    (9 => J),
352    (8 => I),
353    (7 => H),
354    (6 => G),
355    (5 => F),
356    (4 => E),
357    (3 => D),
358    (2 => C),
359    (1 => B),
360    (0 => A),
361}
362
363#[cfg(test)]
364mod tests {
365    use super::*;
366    #[cfg(feature = "alloc")]
367    use alloc::{borrow::ToOwned, vec};
368    #[cfg(feature = "alloc")]
369    use frunk_core::hlist;
370
371    macro_rules! semigroup_tests {
372      ($($name:ident, $comb: expr => $expected: expr, $tr:ty)+) => {
373        $(
374          #[test]
375          fn $name() {
376            let r: $tr = $comb;
377            assert_eq!(r, $expected)
378          }
379        )*
380      }
381    }
382
383    semigroup_tests! {
384        test_i8, 1.combine(&2) => 3, i8
385        test_product_i8, Product(1).combine(&Product(2)) => Product(2), Product<i8>
386        test_i16, 1.combine(&2) => 3, i16
387        test_i32, 1.combine(&2) => 3, i32
388        test_u8, 1.combine(&2) => 3, u8
389        test_u16, 1.combine(&2) => 3, u16
390        test_u32, 1.combine(&2) => 3, u32
391        test_usize, 1.combine(&2) => 3, usize
392        test_isize, 1.combine(&2) => 3, isize
393        test_f32, 1f32.combine(&2f32) => 3f32, f32
394        test_f64, 1f64.combine(&2f64) => 3f64, f64
395        test_option_i16, Some(1).combine(&Some(2)) => Some(3), Option<i16>
396        test_option_i16_none1, None.combine(&Some(2)) => Some(2), Option<i16>
397        test_option_i16_none2, Some(2).combine(&None) => Some(2), Option<i16>
398    }
399
400    #[test]
401    #[cfg(feature = "alloc")]
402    fn test_string() {
403        let v1 = String::from("Hello");
404        let v2 = String::from(" world");
405        assert_eq!(v1.combine(&v2), "Hello world")
406    }
407
408    #[test]
409    #[cfg(feature = "alloc")]
410    fn test_vec_i32() {
411        let v1 = vec![1, 2, 3];
412        let v2 = vec![4, 5, 6];
413        assert_eq!(v1.combine(&v2), vec![1, 2, 3, 4, 5, 6])
414    }
415
416    #[test]
417    fn test_refcell() {
418        let v1 = RefCell::new(1);
419        let v2 = RefCell::new(2);
420        assert_eq!(v1.combine(&v2), RefCell::new(3))
421    }
422
423    #[test]
424    #[cfg(feature = "std")]
425    fn test_hashset() {
426        let mut v1 = HashSet::new();
427        v1.insert(1);
428        v1.insert(2);
429        assert!(!v1.contains(&3));
430        let mut v2 = HashSet::new();
431        v2.insert(3);
432        v2.insert(4);
433        assert!(!v2.contains(&1));
434        let mut expected = HashSet::new();
435        expected.insert(1);
436        expected.insert(2);
437        expected.insert(3);
438        expected.insert(4);
439        assert_eq!(v1.combine(&v2), expected)
440    }
441
442    #[test]
443    #[cfg(feature = "std")]
444    fn test_tuple() {
445        let t1 = (1, 2.5f32, String::from("hi"), Some(3));
446        let t2 = (1, 2.5f32, String::from(" world"), None);
447
448        let expected = (2, 5.0f32, String::from("hi world"), Some(3));
449
450        assert_eq!(t1.combine(&t2), expected)
451    }
452
453    #[test]
454    fn test_max() {
455        assert_eq!(Max(1).combine(&Max(2)), Max(2));
456
457        let v = [Max(1), Max(2), Max(3)];
458        assert_eq!(combine_all_option(&v), Some(Max(3)));
459    }
460
461    #[test]
462    fn test_min() {
463        assert_eq!(Min(1).combine(&Min(2)), Min(1));
464
465        let v = [Min(1), Min(2), Min(3)];
466        assert_eq!(combine_all_option(&v), Some(Min(1)));
467    }
468
469    #[test]
470    fn test_all() {
471        assert_eq!(All(3).combine(&All(5)), All(1));
472        assert_eq!(All(true).combine(&All(false)), All(false));
473    }
474
475    #[test]
476    fn test_any() {
477        assert_eq!(Any(3).combine(&Any(5)), Any(7));
478        assert_eq!(Any(true).combine(&Any(false)), Any(true));
479    }
480
481    #[test]
482    #[cfg(feature = "std")]
483    fn test_hashmap() {
484        let mut v1: HashMap<i32, Option<String>> = HashMap::new();
485        v1.insert(1, Some("Hello".to_owned()));
486        v1.insert(2, Some("Goodbye".to_owned()));
487        v1.insert(4, None);
488        let mut v2: HashMap<i32, Option<String>> = HashMap::new();
489        v2.insert(1, Some(" World".to_owned()));
490        v2.insert(4, Some("Nope".to_owned()));
491        let mut expected = HashMap::new();
492        expected.insert(1, Some("Hello World".to_owned()));
493        expected.insert(2, Some("Goodbye".to_owned()));
494        expected.insert(4, Some("Nope".to_owned()));
495        assert_eq!(v1.combine(&v2), expected)
496    }
497
498    #[test]
499    fn test_combine_all_option() {
500        let v1 = [1, 2, 3];
501        assert_eq!(combine_all_option(&v1), Some(6));
502        let v2 = [Some(1), Some(2), Some(3)];
503        assert_eq!(combine_all_option(&v2), Some(Some(6)));
504    }
505
506    #[test]
507    fn test_combine_n() {
508        assert_eq!(combine_n(&1, 3), 3);
509        assert_eq!(combine_n(&2, 1), 2);
510        assert_eq!(combine_n(&Some(2), 4), Some(8));
511    }
512
513    #[test]
514    #[cfg(feature = "alloc")]
515    fn test_combine_hlist() {
516        let h1 = hlist![Some(1), 3.3, 53i64, "hello".to_owned()];
517        let h2 = hlist![Some(2), 1.2, 1i64, " world".to_owned()];
518        let h3 = hlist![Some(3), 4.5, 54, "hello world".to_owned()];
519        assert_eq!(h1.combine(&h2), h3)
520    }
521}
frunk/semigroup.rs

frunk/
semigroup.rs
