karpal_core/
foldable.rs

1#[cfg(any(feature = "std", feature = "alloc"))]
2use crate::hkt::VecF;
3use crate::hkt::{HKT, OptionF, ResultF};
4use crate::monoid::Monoid;
5
6/// Foldable: a structure that can be folded to a summary value.
7///
8/// Laws:
9/// - fold_map consistency: `fold_map(fa, f) == fold_right(fa, M::empty(), |a, acc| f(a).combine(acc))`
10pub trait Foldable: HKT {
11    fn fold_right<A, B>(fa: Self::Of<A>, init: B, f: impl Fn(A, B) -> B) -> B;
12
13    fn fold_map<A, M: Monoid>(fa: Self::Of<A>, f: impl Fn(A) -> M) -> M {
14        Self::fold_right(fa, M::empty(), |a, acc| f(a).combine(acc))
15    }
16}
17
18impl Foldable for OptionF {
19    fn fold_right<A, B>(fa: Option<A>, init: B, f: impl Fn(A, B) -> B) -> B {
20        match fa {
21            Some(a) => f(a, init),
22            None => init,
23        }
24    }
25}
26
27impl<E> Foldable for ResultF<E> {
28    fn fold_right<A, B>(fa: Result<A, E>, init: B, f: impl Fn(A, B) -> B) -> B {
29        match fa {
30            Ok(a) => f(a, init),
31            Err(_) => init,
32        }
33    }
34}
35
36#[cfg(any(feature = "std", feature = "alloc"))]
37impl Foldable for VecF {
38    fn fold_right<A, B>(fa: Vec<A>, init: B, f: impl Fn(A, B) -> B) -> B {
39        fa.into_iter().rev().fold(init, |acc, a| f(a, acc))
40    }
41}
42
43impl Foldable for crate::hkt::IdentityF {
44    fn fold_right<A, B>(fa: A, init: B, f: impl Fn(A, B) -> B) -> B {
45        f(fa, init)
46    }
47}
48
49#[cfg(any(feature = "std", feature = "alloc"))]
50impl Foldable for crate::hkt::NonEmptyVecF {
51    fn fold_right<A, B>(fa: crate::hkt::NonEmptyVec<A>, init: B, f: impl Fn(A, B) -> B) -> B {
52        let mut acc = init;
53        for a in fa.tail.into_iter().rev() {
54            acc = f(a, acc);
55        }
56        f(fa.head, acc)
57    }
58}
59
60#[cfg(test)]
61mod tests {
62    use super::*;
63
64    #[test]
65    fn option_fold_right_some() {
66        assert_eq!(OptionF::fold_right(Some(3), 10, |a, b| a + b), 13);
67    }
68
69    #[test]
70    fn option_fold_right_none() {
71        assert_eq!(OptionF::fold_right(None::<i32>, 10, |a, b| a + b), 10);
72    }
73
74    #[test]
75    fn result_fold_right_ok() {
76        assert_eq!(ResultF::<&str>::fold_right(Ok(5), 10, |a, b| a + b), 15);
77    }
78
79    #[test]
80    fn result_fold_right_err() {
81        assert_eq!(
82            ResultF::<&str>::fold_right(Err("bad"), 10, |a: i32, b| a + b),
83            10
84        );
85    }
86
87    #[test]
88    fn vec_fold_right() {
89        // fold_right [1,2,3] with init=0 and f(a,b) = a - b
90        // = 1 - (2 - (3 - 0)) = 1 - (2 - 3) = 1 - (-1) = 2
91        assert_eq!(VecF::fold_right(vec![1, 2, 3], 0, |a, b| a - b), 2);
92    }
93
94    #[test]
95    fn vec_fold_map() {
96        let result = VecF::fold_map(vec![1, 2, 3], |a: i32| a);
97        assert_eq!(result, 6); // 1 + 2 + 3
98    }
99}
100
101#[cfg(test)]
102mod law_tests {
103    use super::*;
104    use crate::semigroup::Semigroup;
105    use proptest::prelude::*;
106
107    proptest! {
108        // fold_map consistency: fold_map(fa, f) == fold_right(fa, M::empty(), |a, acc| f(a).combine(acc))
109        #[test]
110        fn option_fold_map_consistency(x in any::<Option<i16>>()) {
111            let f = |a: i16| a as i32;
112            let left = OptionF::fold_map(x, f);
113            let right = OptionF::fold_right(x, i32::empty(), |a, acc| f(a).combine(acc));
114            prop_assert_eq!(left, right);
115        }
116
117        #[test]
118        fn vec_fold_map_consistency(x in prop::collection::vec(0i16..100, 0..10)) {
119            let f = |a: i16| a as i32;
120            let left = VecF::fold_map(x.clone(), f);
121            let right = VecF::fold_right(x, i32::empty(), |a, acc| f(a).combine(acc));
122            prop_assert_eq!(left, right);
123        }
124    }
125}
karpal_core/foldable.rs

karpal_core/
foldable.rs
