fp_library/typeclasses/
traversable.rs

1use crate::{
2	functions::{identity, map},
3	hkt::Apply0L1T,
4	typeclasses::{Applicative, ClonableFn, Foldable, Functor, clonable_fn::ApplyFn},
5};
6
7/// A typeclass for traversable functors.
8///
9/// `Traversable` functors can be traversed, which accumulates results and effects in some [`Applicative`] context.
10///
11/// A minimum implementation of `Traversable` requires the manual implementation of at least [`Traversable::traverse`] or [`Traversable::sequence`].
12pub trait Traversable: Functor + Foldable {
13	/// Map each element of the [`Traversable`] structure to a computation, evaluate those computations and combine the results into an [`Applicative`] context.
14	///
15	/// The default implementation of `traverse` is implemented in terms of [`sequence`] and [`map`] where:
16	///
17	/// `(traverse f) ta = sequence ((map f) ta)`
18	///
19	/// # Type Signature
20	///
21	/// `forall t f a b. Traversable t, Applicative f => (a -> f b) -> t a -> f (t b)`
22	///
23	/// # Parameters
24	///
25	/// * `f`: A function that inputs the elements in the [`Traversable`] structure and outputs applicative computations for each.
26	/// * `ta`: A [`Traversable`] structure containing values.
27	///
28	/// # Returns
29	///
30	/// An [`Applicative`] containing the accumulated results of the computations.
31	///
32	/// # Examples
33	///
34	/// ```
35	/// use fp_library::{brands::{VecBrand, OptionBrand, RcFnBrand}, functions::traverse};
36	/// use std::rc::Rc;
37	///
38	/// assert_eq!(
39	///     traverse::<RcFnBrand, VecBrand, OptionBrand, i32, i32>(Rc::new(|x| Some(x * 2)))(vec![1, 2, 3]),
40	///     Some(vec![2, 4, 6])
41	/// );
42	/// ```
43	fn traverse<
44		'a,
45		ClonableFnBrand: 'a + ClonableFn,
46		F: Applicative,
47		A: 'a + Clone,
48		B: 'a + Clone,
49	>(
50		f: ApplyFn<'a, ClonableFnBrand, A, Apply0L1T<F, B>>
51	) -> ApplyFn<'a, ClonableFnBrand, Apply0L1T<Self, A>, Apply0L1T<F, Apply0L1T<Self, B>>>
52	where
53		Apply0L1T<F, B>: Clone,
54		Apply0L1T<F, ApplyFn<'a, ClonableFnBrand, Apply0L1T<Self, B>, Apply0L1T<Self, B>>>: Clone,
55		Apply0L1T<Self, B>: 'a,
56		Apply0L1T<Self, Apply0L1T<F, B>>: 'a,
57	{
58		ClonableFnBrand::new(move |ta| {
59			Self::sequence::<ClonableFnBrand, F, B>(
60				map::<ClonableFnBrand, Self, _, Apply0L1T<F, B>>(f.clone())(ta),
61			)
62		})
63	}
64
65	/// Evaluate each computation in a [`Traversable`] structure and accumulate the results into an [`Applicative`] context.
66	///
67	/// The default implementation of `sequence` is implemented in terms of [`traverse`] and [`identity`] where:
68	///
69	/// `sequence = traverse identity`
70	///
71	/// # Type Signature
72	///
73	/// `forall t f a. Traversable t, Applicative f => t (f a) -> f (t a)`
74	///
75	/// # Parameters
76	///
77	/// * `t`: A [`Traversable`] structure containing [`Applicative`] computations.
78	///
79	/// # Returns
80	///
81	/// An [`Applicative`] containing the accumulated results of the computations.
82	///
83	/// # Examples
84	///
85	/// ```
86	/// use fp_library::{brands::{VecBrand, OptionBrand, RcFnBrand}, functions::sequence};
87	///
88	/// assert_eq!(
89	///     sequence::<RcFnBrand, VecBrand, OptionBrand, i32>(vec![Some(1), Some(2), Some(3)]),
90	///     Some(vec![1, 2, 3])
91	/// );
92	/// ```
93	fn sequence<'a, ClonableFnBrand: 'a + ClonableFn, F: Applicative, A: 'a + Clone>(
94		t: Apply0L1T<Self, Apply0L1T<F, A>>
95	) -> Apply0L1T<F, Apply0L1T<Self, A>>
96	where
97		Apply0L1T<F, A>: 'a + Clone,
98		Apply0L1T<F, ApplyFn<'a, ClonableFnBrand, Apply0L1T<Self, A>, Apply0L1T<Self, A>>>: Clone,
99		Apply0L1T<Self, A>: 'a,
100		Apply0L1T<Self, Apply0L1T<F, A>>: 'a,
101		Apply0L1T<F, Apply0L1T<Self, A>>: 'a,
102	{
103		(Self::traverse::<ClonableFnBrand, F, _, A>(ClonableFnBrand::new(identity)))(t)
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 typeclass' associated function][`Traversable::traverse`].
110///
111/// The default implementation of `traverse` is implemented in terms of [`sequence`] and [`map`] where:
112///
113/// `(traverse f) ta = sequence ((map f) ta)`
114///
115/// # Type Signature
116///
117/// `forall t f a b. Traversable t, Applicative f => (a -> f b) -> t a -> f (t b)`
118///
119/// # Parameters
120///
121/// * `f`: A function that inputs the elements in the [`Traversable`] structure and outputs applicative computations for each.
122/// * `ta`: A [`Traversable`] structure containing values.
123///
124/// # Returns
125///
126/// An [`Applicative`] containing the accumulated results of the computations.
127///
128/// # Examples
129///
130/// ```
131/// use fp_library::{brands::{VecBrand, OptionBrand, RcFnBrand}, functions::traverse};
132/// use std::rc::Rc;
133///
134/// assert_eq!(
135///     traverse::<RcFnBrand, VecBrand, OptionBrand, i32, i32>(Rc::new(|x| Some(x * 2)))(vec![1, 2, 3]),
136///     Some(vec![2, 4, 6])
137/// );
138/// ```
139pub fn traverse<
140	'a,
141	ClonableFnBrand: 'a + ClonableFn,
142	Brand: Traversable,
143	F: Applicative,
144	A: 'a + Clone,
145	B: 'a + Clone,
146>(
147	f: ApplyFn<'a, ClonableFnBrand, A, Apply0L1T<F, B>>
148) -> ApplyFn<'a, ClonableFnBrand, Apply0L1T<Brand, A>, Apply0L1T<F, Apply0L1T<Brand, B>>>
149where
150	Apply0L1T<F, B>: Clone,
151	Apply0L1T<F, ApplyFn<'a, ClonableFnBrand, Apply0L1T<Brand, B>, Apply0L1T<Brand, B>>>: Clone,
152	Apply0L1T<Brand, B>: 'a,
153	Apply0L1T<Brand, Apply0L1T<F, B>>: 'a,
154{
155	Brand::traverse::<ClonableFnBrand, F, _, B>(f)
156}
157
158/// Evaluate each computation in a [`Traversable`] structure and accumulate the results into an [`Applicative`] context.
159///
160/// Free function version that dispatches to [the typeclass' associated function][`Traversable::sequence`].
161///
162/// The default implementation of `sequence` is implemented in terms of [`traverse`] and [`identity`] where:
163///
164/// `sequence = traverse identity`
165///
166/// # Type Signature
167///
168/// `forall t f a. Traversable t, Applicative f => t (f a) -> f (t a)`
169///
170/// # Parameters
171///
172/// * `t`: A [`Traversable`] structure containing [`Applicative`] computations.
173///
174/// # Returns
175///
176/// An [`Applicative`] containing the accumulated results of the computations.
177///
178/// # Examples
179///
180/// ```
181/// use fp_library::{brands::{VecBrand, OptionBrand, RcFnBrand}, functions::sequence};
182/// use std::rc::Rc;
183///
184/// assert_eq!(
185///     sequence::<RcFnBrand, VecBrand, OptionBrand, i32>(vec![Some(1), Some(2), Some(3)]),
186///     Some(vec![1, 2, 3])
187/// );
188/// ```
189pub fn sequence<
190	'a,
191	ClonableFnBrand: 'a + ClonableFn,
192	Brand: Traversable,
193	F: Applicative,
194	A: 'a + Clone,
195>(
196	t: Apply0L1T<Brand, Apply0L1T<F, A>>
197) -> Apply0L1T<F, Apply0L1T<Brand, A>>
198where
199	Apply0L1T<F, A>: 'a + Clone,
200	Apply0L1T<F, ApplyFn<'a, ClonableFnBrand, Apply0L1T<Brand, A>, Apply0L1T<Brand, A>>>: Clone,
201	Apply0L1T<Brand, A>: 'a,
202	Apply0L1T<Brand, Apply0L1T<F, A>>: 'a,
203	Apply0L1T<F, Apply0L1T<Brand, A>>: 'a,
204{
205	Brand::sequence::<ClonableFnBrand, F, A>(t)
206}
fp_library/typeclasses/traversable.rs

fp_library/typeclasses/
traversable.rs
