karpal_core/
traversable.rs

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

karpal_core/
traversable.rs
