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

karpal_core/
foldable.rs
