fp_library/classes/
par_foldable.rs

1//! A type class for data structures that can be folded in parallel.
2//!
3//! **Note: The `rayon` feature must be enabled to use parallel iteration.**
4//!
5//! ### Examples
6//!
7//! ```
8//! use fp_library::{brands::*, functions::*};
9//!
10//! let v = vec![1, 2, 3, 4, 5];
11//! let f = send_cloneable_fn_new::<ArcFnBrand, _, _>(|x: i32| x.to_string());
12//! let result: String = par_fold_map::<ArcFnBrand, VecBrand, _, _>(f, v);
13//! assert_eq!(result, "12345");
14//! ```
15
16use super::{foldable::Foldable, monoid::Monoid, send_cloneable_fn::SendCloneableFn};
17use crate::{Apply, kinds::*, types::SendEndofunction};
18
19/// A type class for data structures that can be folded in parallel.
20///
21/// This trait provides parallel versions of `Foldable` operations that require
22/// `Send + Sync` bounds on elements and functions. It uses the branded
23/// `SendOf` function type to maintain the library's HKT abstraction.
24///
25/// **Note: The `rayon` feature must be enabled to use parallel iteration.**
26///
27/// ### Minimal Implementation
28///
29/// A minimal implementation requires [`ParFoldable::par_fold_map`].
30///
31/// ### Thread Safety
32///
33/// All operations in this trait are designed to be safe for parallel execution:
34/// - Element type `A` must be `Send + Sync`
35/// - Accumulator/result types must be `Send + Sync`
36/// - Functions are wrapped in `FnBrand::SendOf` which guarantees `Send + Sync`
37///
38/// ### Why is `FnBrand` a Trait-Level Parameter?
39///
40/// Unlike [`Foldable`] where `FnBrand` is a method-level generic parameter
41/// and functions are raw `Fn` types wrapped internally, `ParFoldable` takes `FnBrand`
42/// at the trait level. This design choice is motivated by:
43///
44/// 1. **Thread-safe function values as first-class HKT types**: Function parameters
45///    like `func` in [`ParFoldable::par_fold_map`] are HKT-applied types via
46///    `Apply!(brand: FnBrand, kind: SendCloneableFn, output: SendOf, ...)`. This allows
47///    the type system to enforce thread-safety at the API boundary.
48///
49/// 2. **Guaranteed `Send + Sync` bounds**: The `output: SendOf` in the `Apply!` macro
50///    ensures the function type carries `Send + Sync` bounds essential for parallel
51///    execution, rather than relying on runtime checks.
52///
53/// 3. **Default implementation requirements**: The default [`ParFoldable::par_fold_right`]
54///    implementation needs to call `<FnBrand as SendCloneableFn>::send_cloneable_fn_new(...)` to
55///    create new wrapped functions. Having `FnBrand` at the trait level makes it
56///    available throughout the implementation.
57///
58/// 4. **Multiple implementations per data structure**: With trait-level parameterization,
59///    a type can implement `ParFoldable<ArcFnBrand>` and potentially other function
60///    brands, allowing callers to choose the appropriate thread-safe function wrapper.
61///
62/// ### Examples
63///
64/// ```
65/// use fp_library::{brands::*, functions::*};
66///
67/// let v = vec![1, 2, 3, 4, 5];
68/// let f = send_cloneable_fn_new::<ArcFnBrand, _, _>(|x: i32| x.to_string());
69/// let result: String = par_fold_map::<ArcFnBrand, VecBrand, _, _>(f, v);
70/// assert_eq!(result, "12345");
71/// ```
72pub trait ParFoldable<FnBrand: SendCloneableFn>: Foldable {
73	/// Parallel version of fold_map.
74	///
75	/// Maps each element to a monoid value using `func`, then combines all values using the monoid's `append` operation. The mapping operations may be executed in parallel.
76	///
77	/// ### Type Signature
78	///
79	/// `forall fn_brand t m a. (ParFoldable t, Monoid m, Send m, Sync m) => (fn_brand a m, t a) -> m`
80	///
81	/// ### Type Parameters
82	///
83	/// * `FnBrand`: The brand of thread-safe function to use (must implement `SendCloneableFn`).
84	/// * `A`: The element type (must be `Send + Sync`).
85	/// * `M`: The monoid type (must be `Send + Sync`).
86	///
87	/// ### Parameters
88	///
89	/// * `func`: The thread-safe function to map each element to a monoid`.
90	/// * `fa`: The foldable structure.
91	///
92	/// ### Returns
93	///
94	/// The combined monoid value
95	///
96	/// ### Examples
97	///
98	/// ```
99	/// use fp_library::{brands::*, functions::*};
100	///
101	/// let v = vec![1, 2, 3, 4, 5];
102	/// let f = send_cloneable_fn_new::<ArcFnBrand, _, _>(|x: i32| x.to_string());
103	/// let result: String = par_fold_map::<ArcFnBrand, VecBrand, _, _>(f, v);
104	/// assert_eq!(result, "12345");
105	/// ```
106	fn par_fold_map<'a, M, A>(
107		func: <FnBrand as SendCloneableFn>::SendOf<'a, A, M>,
108		fa: Apply!(<Self as Kind!( type Of<'a, T: 'a>: 'a; )>::Of<'a, A>),
109	) -> M
110	where
111		A: 'a + Clone + Send + Sync,
112		M: Monoid + Send + Sync + 'a;
113
114	/// Parallel version of fold_right.
115	///
116	/// Folds the structure by applying a function from right to left, potentially in parallel.
117	///
118	/// ### Type Signature
119	///
120	/// `forall fn_brand t b a. ParFoldable t => (fn_brand (a, b) b, b, t a) -> b`
121	///
122	/// ### Type Parameters
123	///
124	/// * `FnBrand`: The brand of thread-safe function to use
125	/// * `A`: The element type (must be `Send + Sync`)
126	/// * `B`: The accumulator type (must be `Send + Sync`)
127	///
128	/// ### Parameters
129	///
130	/// * `func`: The thread-safe function to apply to each element and the accumulator.
131	/// * `initial`: The initial value of the accumulator.
132	/// * `fa`: The structure to fold.
133	///
134	/// ### Returns
135	///
136	/// The final accumulator value
137	///
138	/// ### Examples
139	///
140	/// ```
141	/// use fp_library::{brands::*, functions::*};
142	///
143	/// let v = vec![1, 2, 3, 4, 5];
144	/// let f = send_cloneable_fn_new::<ArcFnBrand, _, _>(|(a, b)| a + b);
145	/// let sum = par_fold_right::<ArcFnBrand, VecBrand, _, _>(f, 10, v);
146	/// assert_eq!(sum, 25);
147	/// ```
148	fn par_fold_right<'a, B, A>(
149		func: <FnBrand as SendCloneableFn>::SendOf<'a, (A, B), B>,
150		init: B,
151		fa: Apply!(<Self as Kind!( type Of<'a, T: 'a>: 'a; )>::Of<'a, A>),
152	) -> B
153	where
154		A: 'a + Clone + Send + Sync,
155		B: Send + Sync + 'a,
156		FnBrand: 'a,
157	{
158		let f_clone = func.clone();
159		let endo = Self::par_fold_map(
160			<FnBrand as SendCloneableFn>::send_cloneable_fn_new(move |a: A| {
161				let f_inner = f_clone.clone();
162				SendEndofunction::<FnBrand, B>::new(
163					<FnBrand as SendCloneableFn>::send_cloneable_fn_new(move |b: B| {
164						f_inner((a.clone(), b))
165					}),
166				)
167			}),
168			fa,
169		);
170		endo.0(init)
171	}
172}
173
174/// Parallel fold_map operation.
175///
176/// Free function version that dispatches to [the type class' associated function][`ParFoldable::par_fold_map`].
177///
178/// ### Type Signature
179///
180/// `forall fn_brand t m a. (ParFoldable t, Monoid m, Send m, Sync m) => (fn_brand a m, t a) -> m`
181///
182/// ### Type Parameters
183///
184/// * `FnBrand`: The brand of thread-safe function to use (must implement `SendCloneableFn`).
185/// * `Brand`: The brand of the foldable structure.
186/// * `M`: The monoid type (must be `Send + Sync`).
187/// * `A`: The element type (must be `Send + Sync`).
188///
189/// ### Parameters
190///
191/// * `func`: The thread-safe function to map each element to a monoid.
192/// * `fa`: The structure to fold.
193///
194/// ### Returns
195///
196/// The combined monoid value.
197///
198/// ### Examples
199///
200/// ```
201/// use fp_library::{brands::*, functions::*};
202///
203/// let v = vec![1, 2, 3, 4, 5];
204/// let f = send_cloneable_fn_new::<ArcFnBrand, _, _>(|x: i32| x.to_string());
205/// let result: String = par_fold_map::<ArcFnBrand, VecBrand, _, _>(f, v);
206/// assert_eq!(result, "12345");
207/// ```
208pub fn par_fold_map<'a, FnBrand, Brand, M, A>(
209	func: <FnBrand as SendCloneableFn>::SendOf<'a, A, M>,
210	fa: Apply!(<Brand as Kind!( type Of<'a, T: 'a>: 'a; )>::Of<'a, A>),
211) -> M
212where
213	FnBrand: SendCloneableFn,
214	Brand: ParFoldable<FnBrand>,
215	A: 'a + Clone + Send + Sync,
216	M: Monoid + Send + Sync + 'a,
217{
218	Brand::par_fold_map::<M, A>(func, fa)
219}
220
221/// Parallel fold_right operation.
222///
223/// Free function version that dispatches to [the type class' associated function][`ParFoldable::par_fold_right`].
224///
225/// ### Type Signature
226///
227/// `forall fn_brand t b a. ParFoldable t => (fn_brand (a, b) b, b, t a) -> b`
228///
229/// ### Type Parameters
230///
231/// * `FnBrand`: The brand of thread-safe function to use.
232/// * `Brand`: The brand of the foldable structure.
233/// * `B`: The accumulator type (must be `Send + Sync`).
234/// * `A`: The element type (must be `Send + Sync`).
235///
236/// ### Parameters
237///
238/// * `func`: The thread-safe function to apply to each element and the accumulator.
239/// * `init`: The initial value of the accumulator.
240/// * `fa`: The structure to fold.
241///
242/// ### Returns
243///
244/// The final accumulator value.
245///
246/// ### Examples
247///
248/// ```
249/// use fp_library::{brands::*, functions::*};
250///
251/// let v = vec![1, 2, 3, 4, 5];
252/// let f = send_cloneable_fn_new::<ArcFnBrand, _, _>(|(a, b)| a + b);
253/// let sum = par_fold_right::<ArcFnBrand, VecBrand, _, _>(f, 10, v);
254/// assert_eq!(sum, 25);
255/// ```
256pub fn par_fold_right<'a, FnBrand, Brand, B, A>(
257	func: <FnBrand as SendCloneableFn>::SendOf<'a, (A, B), B>,
258	init: B,
259	fa: Apply!(<Brand as Kind!( type Of<'a, T: 'a>: 'a; )>::Of<'a, A>),
260) -> B
261where
262	FnBrand: SendCloneableFn,
263	Brand: ParFoldable<FnBrand>,
264	A: 'a + Clone + Send + Sync,
265	B: Send + Sync + 'a,
266	FnBrand: 'a,
267{
268	Brand::par_fold_right::<B, A>(func, init, fa)
269}
fp_library/classes/par_foldable.rs

fp_library/classes/
par_foldable.rs
