karpal_core/
traversable.rs

1use crate::applicative::Applicative;
2use crate::foldable::Foldable;
3use crate::functor::Functor;
4#[cfg(any(feature = "std", feature = "alloc"))]
5use crate::hkt::VecF;
6use crate::hkt::{OptionF, ResultF};
7#[cfg(all(not(feature = "std"), feature = "alloc"))]
8use alloc::vec::Vec;
9
10/// Traversable: a Functor + Foldable that can be traversed with an effect.
11///
12/// Laws:
13/// - Identity: `traverse::<IdentityF, _, _, _, _>(fa, pure) == pure(fa)`
14///   (We test with OptionF as the effect.)
15pub trait Traversable: Functor + Foldable {
16    fn traverse<G, A, B, F>(fa: Self::Of<A>, f: F) -> G::Of<Self::Of<B>>
17    where
18        G: Applicative,
19        F: Fn(A) -> G::Of<B>,
20        B: Clone;
21}
22
23impl Traversable for OptionF {
24    fn traverse<G, A, B, F>(fa: Option<A>, f: F) -> G::Of<Option<B>>
25    where
26        G: Applicative,
27        F: Fn(A) -> G::Of<B>,
28        B: Clone,
29    {
30        match fa {
31            None => G::pure(None),
32            Some(a) => G::fmap(f(a), |b| Some(b)),
33        }
34    }
35}
36
37impl<E: Clone> Traversable for ResultF<E> {
38    fn traverse<G, A, B, F>(fa: Result<A, E>, f: F) -> G::Of<Result<B, E>>
39    where
40        G: Applicative,
41        F: Fn(A) -> G::Of<B>,
42        B: Clone,
43    {
44        match fa {
45            Err(e) => G::pure(Err(e)),
46            Ok(a) => G::fmap(f(a), Ok),
47        }
48    }
49}
50
51#[cfg(any(feature = "std", feature = "alloc"))]
52impl Traversable for VecF {
53    fn traverse<G, A, B, F>(fa: Vec<A>, f: F) -> G::Of<Vec<B>>
54    where
55        G: Applicative,
56        F: Fn(A) -> G::Of<B>,
57        B: Clone,
58    {
59        let init: G::Of<Vec<B>> = G::pure(Vec::new());
60        fa.into_iter().fold(init, |acc, a| {
61            let gb = f(a);
62            G::ap(
63                G::fmap(acc, |v: Vec<B>| {
64                    move |b: B| {
65                        let mut v = v.clone();
66                        v.push(b);
67                        v
68                    }
69                }),
70                gb,
71            )
72        })
73    }
74}
75
76#[cfg(test)]
77mod tests {
78    use super::*;
79
80    #[test]
81    fn option_traverse_some() {
82        let result = OptionF::traverse::<OptionF, _, _, _>(Some(3), |x| Some(x * 2));
83        assert_eq!(result, Some(Some(6)));
84    }
85
86    #[test]
87    fn option_traverse_none() {
88        let result = OptionF::traverse::<OptionF, i32, i32, _>(None, |x| Some(x * 2));
89        assert_eq!(result, Some(None));
90    }
91
92    #[test]
93    fn option_traverse_effect_fails() {
94        let result = OptionF::traverse::<OptionF, _, _, _>(Some(3), |_x| None::<i32>);
95        assert_eq!(result, None);
96    }
97
98    #[test]
99    fn result_traverse_ok() {
100        let result = ResultF::<&str>::traverse::<OptionF, _, _, _>(Ok(3), |x| Some(x * 2));
101        assert_eq!(result, Some(Ok(6)));
102    }
103
104    #[test]
105    fn result_traverse_err() {
106        let result = ResultF::<&str>::traverse::<OptionF, i32, i32, _>(Err("bad"), |x| Some(x * 2));
107        assert_eq!(result, Some(Err("bad")));
108    }
109
110    #[test]
111    fn vec_traverse_all_some() {
112        let result = VecF::traverse::<OptionF, _, _, _>(vec![1, 2, 3], |x| Some(x * 2));
113        assert_eq!(result, Some(vec![2, 4, 6]));
114    }
115
116    #[test]
117    fn vec_traverse_one_none() {
118        let result = VecF::traverse::<OptionF, _, _, _>(vec![1, 2, 3], |x| {
119            if x == 2 { None } else { Some(x * 2) }
120        });
121        assert_eq!(result, None);
122    }
123
124    #[test]
125    fn vec_traverse_empty() {
126        let result = VecF::traverse::<OptionF, i32, i32, _>(vec![], |x| Some(x * 2));
127        assert_eq!(result, Some(vec![]));
128    }
129}
130
131#[cfg(test)]
132mod law_tests {
133    use super::*;
134    use proptest::prelude::*;
135
136    proptest! {
137        // Identity: traverse(fa, Some) == Some(fa)
138        #[test]
139        fn option_identity(x in any::<Option<i32>>()) {
140            let result = OptionF::traverse::<OptionF, _, _, _>(x, Some);
141            prop_assert_eq!(result, Some(x));
142        }
143
144        #[test]
145        fn vec_identity(x in prop::collection::vec(any::<i32>(), 0..10)) {
146            let result = VecF::traverse::<OptionF, _, _, _>(x.clone(), Some);
147            prop_assert_eq!(result, Some(x));
148        }
149    }
150}
karpal_core/traversable.rs

karpal_core/
traversable.rs
