karpal_core/
foldable.rs

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

karpal_core/
foldable.rs
