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