fp_library/classes/
par_foldable.rs

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

fp_library/classes/
par_foldable.rs
