fp_library/classes/
traversable.rs

1use super::{applicative::Applicative, foldable::Foldable, functor::Functor};
2use crate::{functions::identity, hkt::Apply1L1T};
3
4/// A type class for traversable functors.
5///
6/// `Traversable` functors can be traversed, which accumulates results and effects in some [`Applicative`] context.
7pub trait Traversable: Functor + Foldable {
8	/// Map each element of the [`Traversable`] structure to a computation, evaluate those computations and combine the results into an [`Applicative`] context.
9	///
10	/// The default implementation is defined in terms of [`sequence`] and [`Functor::map`].
11	///
12	/// **Note**: This default implementation may be less efficient than a direct implementation because it performs two passes:
13	/// first mapping the function to create an intermediate structure of computations, and then sequencing that structure.
14	/// A direct implementation can often perform the traversal in a single pass without allocating an intermediate container.
15	/// Types should provide their own implementation if possible.
16	///
17	/// # Type Signature
18	///
19	/// `forall a b f. (Traversable t, Applicative f) => (a -> f b, t a) -> f (t b)`
20	///
21	/// # Parameters
22	///
23	/// * `f`: The function to apply to each element, returning a value in an applicative context.
24	/// * `ta`: The traversable structure.
25	///
26	/// # Returns
27	///
28	/// The traversable structure wrapped in the applicative context.
29	///
30	/// # Examples
31	///
32	/// ```
33	/// use fp_library::classes::traversable::Traversable;
34	/// use fp_library::brands::OptionBrand;
35	///
36	/// let x = Some(5);
37	/// let y = OptionBrand::traverse::<OptionBrand, _, _, _>(|a| Some(a * 2), x);
38	/// assert_eq!(y, Some(Some(10)));
39	/// ```
40	fn traverse<'a, F: Applicative, A: 'a + Clone, B: 'a + Clone, Func>(
41		f: Func,
42		ta: Apply1L1T<'a, Self, A>,
43	) -> Apply1L1T<'a, F, Apply1L1T<'a, Self, B>>
44	where
45		Func: Fn(A) -> Apply1L1T<'a, F, B> + 'a,
46		Apply1L1T<'a, Self, B>: Clone,
47		Apply1L1T<'a, F, B>: Clone,
48	{
49		Self::sequence::<F, B>(Self::map(f, ta))
50	}
51
52	/// Evaluate each computation in a [`Traversable`] structure and accumulate the results into an [`Applicative`] context.
53	///
54	/// The default implementation is defined in terms of [`traverse`] and [`identity`].
55	///
56	/// # Type Signature
57	///
58	/// `forall a f. (Traversable t, Applicative f) => (t (f a)) -> f (t a)`
59	///
60	/// # Parameters
61	///
62	/// * `ta`: The traversable structure containing values in an applicative context.
63	///
64	/// # Returns
65	///
66	/// The traversable structure wrapped in the applicative context.
67	///
68	/// # Examples
69	///
70	/// ```
71	/// use fp_library::classes::traversable::Traversable;
72	/// use fp_library::brands::OptionBrand;
73	///
74	/// let x = Some(Some(5));
75	/// let y = OptionBrand::sequence::<OptionBrand, _>(x);
76	/// assert_eq!(y, Some(Some(5)));
77	/// ```
78	fn sequence<'a, F: Applicative, A: 'a + Clone>(
79		ta: Apply1L1T<'a, Self, Apply1L1T<'a, F, A>>
80	) -> Apply1L1T<'a, F, Apply1L1T<'a, Self, A>>
81	where
82		Apply1L1T<'a, F, A>: Clone,
83		Apply1L1T<'a, Self, A>: Clone,
84	{
85		Self::traverse::<F, Apply1L1T<'a, F, A>, A, _>(identity, ta)
86	}
87}
88
89/// Map each element of the [`Traversable`] structure to a computation, evaluate those computations and combine the results into an [`Applicative`] context.
90///
91/// Free function version that dispatches to [the type class' associated function][`Traversable::traverse`].
92///
93/// # Type Signature
94///
95/// `forall a b f. (Traversable t, Applicative f) => (a -> f b, t a) -> f (t b)`
96///
97/// # Parameters
98///
99/// * `f`: The function to apply to each element, returning a value in an applicative context.
100/// * `ta`: The traversable structure.
101///
102/// # Returns
103///
104/// The traversable structure wrapped in the applicative context.
105///
106/// # Examples
107///
108/// ```
109/// use fp_library::classes::traversable::traverse;
110/// use fp_library::brands::OptionBrand;
111///
112/// let x = Some(5);
113/// let y = traverse::<OptionBrand, OptionBrand, _, _, _>(|a| Some(a * 2), x);
114/// assert_eq!(y, Some(Some(10)));
115/// ```
116pub fn traverse<'a, Brand: Traversable, F: Applicative, A: 'a + Clone, B: 'a + Clone, Func>(
117	f: Func,
118	ta: Apply1L1T<'a, Brand, A>,
119) -> Apply1L1T<'a, F, Apply1L1T<'a, Brand, B>>
120where
121	Func: Fn(A) -> Apply1L1T<'a, F, B> + 'a,
122	Apply1L1T<'a, Brand, B>: Clone,
123	Apply1L1T<'a, F, B>: Clone,
124{
125	Brand::traverse::<F, A, B, Func>(f, ta)
126}
127
128/// Evaluate each computation in a [`Traversable`] structure and accumulate the results into an [`Applicative`] context.
129///
130/// Free function version that dispatches to [the type class' associated function][`Traversable::sequence`].
131///
132/// # Type Signature
133///
134/// `forall a f. (Traversable t, Applicative f) => (t (f a)) -> f (t a)`
135///
136/// # Parameters
137///
138/// * `ta`: The traversable structure containing values in an applicative context.
139///
140/// # Returns
141///
142/// The traversable structure wrapped in the applicative context.
143///
144/// # Examples
145///
146/// ```
147/// use fp_library::classes::traversable::sequence;
148/// use fp_library::brands::OptionBrand;
149///
150/// let x = Some(Some(5));
151/// let y = sequence::<OptionBrand, OptionBrand, _>(x);
152/// assert_eq!(y, Some(Some(5)));
153/// ```
154pub fn sequence<'a, Brand: Traversable, F: Applicative, A: 'a + Clone>(
155	ta: Apply1L1T<'a, Brand, Apply1L1T<'a, F, A>>
156) -> Apply1L1T<'a, F, Apply1L1T<'a, Brand, A>>
157where
158	Apply1L1T<'a, F, A>: Clone,
159	Apply1L1T<'a, Brand, A>: Clone,
160{
161	Brand::sequence::<F, A>(ta)
162}
fp_library/classes/traversable.rs

fp_library/classes/
traversable.rs
