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