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