fp_library/classes/
bifoldable.rs

1//! Data structures with two type arguments that can be folded into a single value.
2//!
3//! ### Examples
4//!
5//! ```
6//! use fp_library::{
7//! 	brands::*,
8//! 	functions::explicit::*,
9//! };
10//!
11//! let x: Result<i32, i32> = Ok(5);
12//! let y = bi_fold_map::<RcFnBrand, ResultBrand, _, _, _, _, _>(
13//! 	(|e: i32| e.to_string(), |s: i32| s.to_string()),
14//! 	x,
15//! );
16//! assert_eq!(y, "5".to_string());
17//! ```
18
19#[fp_macros::document_module]
20mod inner {
21	use {
22		crate::{
23			classes::*,
24			kinds::*,
25			types::*,
26		},
27		fp_macros::*,
28	};
29
30	/// A type class for data structures with two type arguments that can be folded.
31	///
32	/// A `Bifoldable` represents a container with two type parameters, where elements
33	/// of either type can be folded into a single result. A fold requires two step
34	/// functions, one for each type argument.
35	///
36	/// ### Minimal Implementation
37	///
38	/// A minimal implementation requires either [`Bifoldable::bi_fold_map`] or
39	/// [`Bifoldable::bi_fold_right`] to be defined directly:
40	///
41	/// * If [`Bifoldable::bi_fold_right`] is implemented, [`Bifoldable::bi_fold_map`]
42	///   and [`Bifoldable::bi_fold_left`] are derived from it.
43	/// * If [`Bifoldable::bi_fold_map`] is implemented, [`Bifoldable::bi_fold_right`]
44	///   is derived via `Endofunction`, and [`Bifoldable::bi_fold_left`] is derived
45	///   from the derived [`Bifoldable::bi_fold_right`].
46	///
47	/// Note: defining both defaults creates a circular dependency and will not terminate.
48	///
49	/// ### Laws
50	///
51	/// `Bifoldable` instances must be internally consistent and consistent with
52	/// `Bifunctor` when one is also defined:
53	/// * bi_fold_map/bi_fold_right consistency: `bi_fold_map(f, g, x) = bi_fold_right(|a, c| append(f(a), c), |b, c| append(g(b), c), empty(), x)`.
54	#[document_examples]
55	///
56	/// Bifoldable laws for [`Result`]:
57	///
58	/// ```
59	/// use fp_library::{
60	/// 	brands::*,
61	/// 	functions::{
62	/// 		explicit::{
63	/// 			bi_fold_map,
64	/// 			bi_fold_right,
65	/// 		},
66	/// 		*,
67	/// 	},
68	/// };
69	///
70	/// // ResultBrand has Of<E, A> = Result<A, E>, so the first function handles errors
71	/// // and the second function handles ok values.
72	/// let ok: Result<i32, String> = Ok(5);
73	/// let err: Result<i32, String> = Err("err".to_string());
74	/// let f = |e: String| format!("err:{e}");
75	/// let g = |a: i32| a.to_string();
76	///
77	/// // bi_fold_map/bi_fold_right consistency (Ok case):
78	/// assert_eq!(
79	/// 	bi_fold_map::<RcFnBrand, ResultBrand, _, _, _, _, _>((f, g), ok.clone()),
80	/// 	bi_fold_right::<RcFnBrand, ResultBrand, _, _, _, _, _>(
81	/// 		(|a: String, c: String| append(f(a), c), |b: i32, c: String| append(g(b), c)),
82	/// 		empty::<String>(),
83	/// 		ok,
84	/// 	),
85	/// );
86	///
87	/// // bi_fold_map/bi_fold_right consistency (Err case):
88	/// assert_eq!(
89	/// 	bi_fold_map::<RcFnBrand, ResultBrand, _, _, _, _, _>((f, g), err.clone()),
90	/// 	bi_fold_right::<RcFnBrand, ResultBrand, _, _, _, _, _>(
91	/// 		(|a: String, c: String| append(f(a), c), |b: i32, c: String| append(g(b), c)),
92	/// 		empty::<String>(),
93	/// 		err,
94	/// 	),
95	/// );
96	/// ```
97	#[kind(type Of<'a, A: 'a, B: 'a>: 'a;)]
98	pub trait Bifoldable {
99		/// Folds the bifoldable structure from right to left using two step functions.
100		///
101		/// This method performs a right-associative fold, dispatching to `f` for
102		/// elements of the first type and `g` for elements of the second type.
103		#[document_signature]
104		///
105		#[document_type_parameters(
106			"The lifetime of the values.",
107			"The brand of the cloneable function to use.",
108			"The type of the first-position elements.",
109			"The type of the second-position elements.",
110			"The type of the accumulator."
111		)]
112		///
113		#[document_parameters(
114			"The step function for first-position elements.",
115			"The step function for second-position elements.",
116			"The initial accumulator value.",
117			"The bifoldable structure to fold."
118		)]
119		///
120		#[document_returns("The final accumulator value after folding all elements.")]
121		#[document_examples]
122		///
123		/// ```
124		/// use fp_library::{
125		/// 	brands::*,
126		/// 	functions::explicit::*,
127		/// };
128		///
129		/// let x: Result<i32, i32> = Err(3);
130		/// let y = bi_fold_right::<RcFnBrand, ResultBrand, _, _, _, _, _>(
131		/// 	(|e, acc| acc - e, |s, acc| acc + s),
132		/// 	10,
133		/// 	x,
134		/// );
135		/// assert_eq!(y, 7);
136		/// ```
137		fn bi_fold_right<'a, FnBrand: LiftFn + 'a, A: 'a + Clone, B: 'a + Clone, C: 'a>(
138			f: impl Fn(A, C) -> C + 'a,
139			g: impl Fn(B, C) -> C + 'a,
140			z: C,
141			p: Apply!(<Self as Kind!( type Of<'a, A: 'a, B: 'a>: 'a; )>::Of<'a, A, B>),
142		) -> C {
143			let f = <FnBrand as LiftFn>::new(move |(a, c)| f(a, c));
144			let g = <FnBrand as LiftFn>::new(move |(b, c)| g(b, c));
145			let endo = Self::bi_fold_map::<FnBrand, A, B, Endofunction<'a, FnBrand, C>>(
146				move |a: A| {
147					let f = f.clone();
148					Endofunction::<FnBrand, C>::new(<FnBrand as LiftFn>::new(move |c| {
149						f((a.clone(), c))
150					}))
151				},
152				move |b: B| {
153					let g = g.clone();
154					Endofunction::<FnBrand, C>::new(<FnBrand as LiftFn>::new(move |c| {
155						g((b.clone(), c))
156					}))
157				},
158				p,
159			);
160			endo.0(z)
161		}
162
163		/// Folds the bifoldable structure from left to right using two step functions.
164		///
165		/// This method performs a left-associative fold, dispatching to `f` for
166		/// elements of the first type and `g` for elements of the second type.
167		#[document_signature]
168		///
169		#[document_type_parameters(
170			"The lifetime of the values.",
171			"The brand of the cloneable function to use.",
172			"The type of the first-position elements.",
173			"The type of the second-position elements.",
174			"The type of the accumulator."
175		)]
176		///
177		#[document_parameters(
178			"The step function for first-position elements.",
179			"The step function for second-position elements.",
180			"The initial accumulator value.",
181			"The bifoldable structure to fold."
182		)]
183		///
184		#[document_returns("The final accumulator value after folding all elements.")]
185		#[document_examples]
186		///
187		/// ```
188		/// use fp_library::{
189		/// 	brands::*,
190		/// 	functions::explicit::*,
191		/// };
192		///
193		/// let x: Result<i32, i32> = Ok(5);
194		/// let y = bi_fold_left::<RcFnBrand, ResultBrand, _, _, _, _, _>(
195		/// 	(|acc, e| acc - e, |acc, s| acc + s),
196		/// 	10,
197		/// 	x,
198		/// );
199		/// assert_eq!(y, 15);
200		/// ```
201		fn bi_fold_left<'a, FnBrand: LiftFn + 'a, A: 'a + Clone, B: 'a + Clone, C: 'a>(
202			f: impl Fn(C, A) -> C + 'a,
203			g: impl Fn(C, B) -> C + 'a,
204			z: C,
205			p: Apply!(<Self as Kind!( type Of<'a, A: 'a, B: 'a>: 'a; )>::Of<'a, A, B>),
206		) -> C {
207			let f = <FnBrand as LiftFn>::new(move |(c, a)| f(c, a));
208			let g = <FnBrand as LiftFn>::new(move |(c, b)| g(c, b));
209			let endo = Self::bi_fold_right::<FnBrand, A, B, Endofunction<'a, FnBrand, C>>(
210				move |a: A, k: Endofunction<'a, FnBrand, C>| {
211					let f = f.clone();
212					let current =
213						Endofunction::<FnBrand, C>::new(<FnBrand as LiftFn>::new(move |c| {
214							f((c, a.clone()))
215						}));
216					Semigroup::append(k, current)
217				},
218				move |b: B, k: Endofunction<'a, FnBrand, C>| {
219					let g = g.clone();
220					let current =
221						Endofunction::<FnBrand, C>::new(<FnBrand as LiftFn>::new(move |c| {
222							g((c, b.clone()))
223						}));
224					Semigroup::append(k, current)
225				},
226				Endofunction::<FnBrand, C>::empty(),
227				p,
228			);
229			endo.0(z)
230		}
231
232		/// Maps elements of both types to a monoid and combines the results.
233		///
234		/// This method maps each element of the first type using `f` and each element
235		/// of the second type using `g`, then combines all results using the monoid's
236		/// `append` operation.
237		#[document_signature]
238		///
239		#[document_type_parameters(
240			"The lifetime of the values.",
241			"The brand of the cloneable function to use.",
242			"The type of the first-position elements.",
243			"The type of the second-position elements.",
244			"The monoid type to fold into."
245		)]
246		///
247		#[document_parameters(
248			"The function mapping first-position elements to the monoid.",
249			"The function mapping second-position elements to the monoid.",
250			"The bifoldable structure to fold."
251		)]
252		///
253		#[document_returns("The combined monoid value.")]
254		#[document_examples]
255		///
256		/// ```
257		/// use fp_library::{
258		/// 	brands::*,
259		/// 	functions::explicit::*,
260		/// };
261		///
262		/// let x: Result<i32, i32> = Ok(5);
263		/// let y = bi_fold_map::<RcFnBrand, ResultBrand, _, _, _, _, _>(
264		/// 	(|e: i32| e.to_string(), |s: i32| s.to_string()),
265		/// 	x,
266		/// );
267		/// assert_eq!(y, "5".to_string());
268		/// ```
269		fn bi_fold_map<'a, FnBrand: LiftFn + 'a, A: 'a + Clone, B: 'a + Clone, M>(
270			f: impl Fn(A) -> M + 'a,
271			g: impl Fn(B) -> M + 'a,
272			p: Apply!(<Self as Kind!( type Of<'a, A: 'a, B: 'a>: 'a; )>::Of<'a, A, B>),
273		) -> M
274		where
275			M: Monoid + 'a, {
276			Self::bi_fold_right::<FnBrand, A, B, M>(
277				move |a, m| M::append(f(a), m),
278				move |b, m| M::append(g(b), m),
279				M::empty(),
280				p,
281			)
282		}
283	}
284
285	/// Folds the bifoldable structure from right to left using two step functions.
286	///
287	/// Free function version that dispatches to [the type class' associated function][`Bifoldable::bi_fold_right`].
288	#[document_signature]
289	///
290	#[document_type_parameters(
291		"The lifetime of the values.",
292		"The brand of the cloneable function to use.",
293		"The brand of the bifoldable structure.",
294		"The type of the first-position elements.",
295		"The type of the second-position elements.",
296		"The type of the accumulator."
297	)]
298	///
299	#[document_parameters(
300		"The step function for first-position elements.",
301		"The step function for second-position elements.",
302		"The initial accumulator value.",
303		"The bifoldable structure to fold."
304	)]
305	///
306	#[document_returns("The final accumulator value after folding all elements.")]
307	#[document_examples]
308	///
309	/// ```
310	/// use fp_library::{
311	/// 	brands::*,
312	/// 	functions::explicit::*,
313	/// };
314	///
315	/// let x: Result<i32, i32> = Err(3);
316	/// let y = bi_fold_right::<RcFnBrand, ResultBrand, _, _, _, _, _>(
317	/// 	(|e, acc| acc - e, |s, acc| acc + s),
318	/// 	10,
319	/// 	x,
320	/// );
321	/// assert_eq!(y, 7);
322	/// ```
323	pub fn bi_fold_right<
324		'a,
325		FnBrand: LiftFn + 'a,
326		Brand: Bifoldable,
327		A: 'a + Clone,
328		B: 'a + Clone,
329		C: 'a,
330	>(
331		f: impl Fn(A, C) -> C + 'a,
332		g: impl Fn(B, C) -> C + 'a,
333		z: C,
334		p: Apply!(<Brand as Kind!( type Of<'a, A: 'a, B: 'a>: 'a; )>::Of<'a, A, B>),
335	) -> C {
336		Brand::bi_fold_right::<FnBrand, A, B, C>(f, g, z, p)
337	}
338
339	/// Folds the bifoldable structure from left to right using two step functions.
340	///
341	/// Free function version that dispatches to [the type class' associated function][`Bifoldable::bi_fold_left`].
342	#[document_signature]
343	///
344	#[document_type_parameters(
345		"The lifetime of the values.",
346		"The brand of the cloneable function to use.",
347		"The brand of the bifoldable structure.",
348		"The type of the first-position elements.",
349		"The type of the second-position elements.",
350		"The type of the accumulator."
351	)]
352	///
353	#[document_parameters(
354		"The step function for first-position elements.",
355		"The step function for second-position elements.",
356		"The initial accumulator value.",
357		"The bifoldable structure to fold."
358	)]
359	///
360	#[document_returns("The final accumulator value after folding all elements.")]
361	#[document_examples]
362	///
363	/// ```
364	/// use fp_library::{
365	/// 	brands::*,
366	/// 	functions::explicit::*,
367	/// };
368	///
369	/// let x: Result<i32, i32> = Ok(5);
370	/// let y = bi_fold_left::<RcFnBrand, ResultBrand, _, _, _, _, _>(
371	/// 	(|acc, e| acc - e, |acc, s| acc + s),
372	/// 	10,
373	/// 	x,
374	/// );
375	/// assert_eq!(y, 15);
376	/// ```
377	pub fn bi_fold_left<
378		'a,
379		FnBrand: LiftFn + 'a,
380		Brand: Bifoldable,
381		A: 'a + Clone,
382		B: 'a + Clone,
383		C: 'a,
384	>(
385		f: impl Fn(C, A) -> C + 'a,
386		g: impl Fn(C, B) -> C + 'a,
387		z: C,
388		p: Apply!(<Brand as Kind!( type Of<'a, A: 'a, B: 'a>: 'a; )>::Of<'a, A, B>),
389	) -> C {
390		Brand::bi_fold_left::<FnBrand, A, B, C>(f, g, z, p)
391	}
392
393	/// Maps elements of both types to a monoid and combines the results.
394	///
395	/// Free function version that dispatches to [the type class' associated function][`Bifoldable::bi_fold_map`].
396	#[document_signature]
397	///
398	#[document_type_parameters(
399		"The lifetime of the values.",
400		"The brand of the cloneable function to use.",
401		"The brand of the bifoldable structure.",
402		"The type of the first-position elements.",
403		"The type of the second-position elements.",
404		"The monoid type to fold into."
405	)]
406	///
407	#[document_parameters(
408		"The function mapping first-position elements to the monoid.",
409		"The function mapping second-position elements to the monoid.",
410		"The bifoldable structure to fold."
411	)]
412	///
413	#[document_returns("The combined monoid value.")]
414	#[document_examples]
415	///
416	/// ```
417	/// use fp_library::{
418	/// 	brands::*,
419	/// 	functions::explicit::*,
420	/// };
421	///
422	/// let x: Result<i32, i32> = Ok(5);
423	/// let y = bi_fold_map::<RcFnBrand, ResultBrand, _, _, _, _, _>(
424	/// 	(|e: i32| e.to_string(), |s: i32| s.to_string()),
425	/// 	x,
426	/// );
427	/// assert_eq!(y, "5".to_string());
428	/// ```
429	pub fn bi_fold_map<
430		'a,
431		FnBrand: LiftFn + 'a,
432		Brand: Bifoldable,
433		A: 'a + Clone,
434		B: 'a + Clone,
435		M,
436	>(
437		f: impl Fn(A) -> M + 'a,
438		g: impl Fn(B) -> M + 'a,
439		p: Apply!(<Brand as Kind!( type Of<'a, A: 'a, B: 'a>: 'a; )>::Of<'a, A, B>),
440	) -> M
441	where
442		M: Monoid + 'a, {
443		Brand::bi_fold_map::<FnBrand, A, B, M>(f, g, p)
444	}
445}
446
447pub use inner::*;
fp_library/classes/bifoldable.rs

fp_library/classes/
bifoldable.rs
