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

karpal_core/
traversable.rs
