fp_library/types/
endofunction.rs

1//! Wrapper for endofunctions (functions `a -> a`) with [`Semigroup`] and [`Monoid`] instances based on function composition.
2//!
3//! Used to treat function composition as a monoidal operation where [`append`](crate::functions::append) composes functions and [`empty`](crate::functions::empty) is the identity function.
4
5use crate::{
6	classes::{CloneableFn, Monoid, Semigroup},
7	functions::identity,
8};
9use fp_macros::{doc_params, hm_signature};
10use std::{
11	fmt::{self, Debug, Formatter},
12	hash::Hash,
13};
14
15/// A wrapper for endofunctions (functions from a set to the same set) that enables monoidal operations.
16///
17/// `Endofunction a` represents a function `a -> a`.
18///
19/// It exists to provide a monoid instance where:
20///
21/// * The binary operation [append][Semigroup::append] is [function composition][crate::functions::compose].
22/// * The identity element [empty][Monoid::empty] is the [identity function][crate::functions::identity].
23///
24/// The wrapped function can be accessed directly via the [`.0` field][Endofunction#structfield.0].
25///
26/// ### Type Parameters
27///
28/// * `FnBrand`: The brand of the cloneable function wrapper.
29/// * `A`: The input and output type of the function.
30///
31/// ### Fields
32///
33/// * `0`: The wrapped function.
34///
35/// ### Examples
36///
37/// ```
38/// use fp_library::{brands::*, functions::*, types::*};
39///
40/// let f = Endofunction::<RcFnBrand, _>::new(cloneable_fn_new::<RcFnBrand, _, _>(|x: i32| x * 2));
41/// assert_eq!(f.0(5), 10);
42/// ```
43pub struct Endofunction<'a, FnBrand: CloneableFn, A>(pub <FnBrand as CloneableFn>::Of<'a, A, A>);
44
45impl<'a, FnBrand: CloneableFn, A> Endofunction<'a, FnBrand, A> {
46	/// Creates a new `Endofunction`.
47	///
48	/// This function wraps a function `a -> a` in an `Endofunction` struct.
49	///
50	/// ### Type Signature
51	///
52	#[hm_signature]
53	///
54	/// ### Type Parameters
55	///
56	/// * `FnBrand`: The brand of the function (e.g., `RcFnBrand`).
57	/// * `A`: The input and output type of the function.
58	///
59	/// ### Parameters
60	///
61	#[doc_params("The function to wrap.")]
62	///
63	/// ### Returns
64	///
65	/// A new `Endofunction`.
66	///
67	/// ### Examples
68	///
69	/// ```
70	/// use fp_library::{brands::*, functions::*, types::*};
71	///
72	/// let f = Endofunction::<RcFnBrand, _>::new(cloneable_fn_new::<RcFnBrand, _, _>(|x: i32| x * 2));
73	/// assert_eq!(f.0(5), 10);
74	/// ```
75	pub fn new(f: <FnBrand as CloneableFn>::Of<'a, A, A>) -> Self {
76		Self(f)
77	}
78}
79
80impl<'a, FnBrand: CloneableFn, A> Clone for Endofunction<'a, FnBrand, A> {
81	fn clone(&self) -> Self {
82		Self::new(self.0.clone())
83	}
84}
85
86impl<'a, FnBrand: CloneableFn, A> Debug for Endofunction<'a, FnBrand, A>
87where
88	<FnBrand as CloneableFn>::Of<'a, A, A>: Debug,
89{
90	fn fmt(
91		&self,
92		fmt: &mut Formatter<'_>,
93	) -> fmt::Result {
94		fmt.debug_tuple("Endofunction").field(&self.0).finish()
95	}
96}
97
98impl<'a, FnBrand: CloneableFn, A> Eq for Endofunction<'a, FnBrand, A> where
99	<FnBrand as CloneableFn>::Of<'a, A, A>: Eq
100{
101}
102
103impl<'a, FnBrand: CloneableFn, A> Hash for Endofunction<'a, FnBrand, A>
104where
105	<FnBrand as CloneableFn>::Of<'a, A, A>: Hash,
106{
107	fn hash<H: std::hash::Hasher>(
108		&self,
109		state: &mut H,
110	) {
111		self.0.hash(state);
112	}
113}
114
115impl<'a, FnBrand: CloneableFn, A> Ord for Endofunction<'a, FnBrand, A>
116where
117	<FnBrand as CloneableFn>::Of<'a, A, A>: Ord,
118{
119	fn cmp(
120		&self,
121		other: &Self,
122	) -> std::cmp::Ordering {
123		self.0.cmp(&other.0)
124	}
125}
126
127impl<'a, FnBrand: CloneableFn, A> PartialEq for Endofunction<'a, FnBrand, A>
128where
129	<FnBrand as CloneableFn>::Of<'a, A, A>: PartialEq,
130{
131	fn eq(
132		&self,
133		other: &Self,
134	) -> bool {
135		self.0 == other.0
136	}
137}
138
139impl<'a, FnBrand: CloneableFn, A> PartialOrd for Endofunction<'a, FnBrand, A>
140where
141	<FnBrand as CloneableFn>::Of<'a, A, A>: PartialOrd,
142{
143	fn partial_cmp(
144		&self,
145		other: &Self,
146	) -> Option<std::cmp::Ordering> {
147		self.0.partial_cmp(&other.0)
148	}
149}
150
151impl<'a, FnBrand: 'a + CloneableFn, A: 'a> Semigroup for Endofunction<'a, FnBrand, A> {
152	/// The result of combining the two values using the semigroup operation.
153	///
154	/// This method composes two endofunctions into a single endofunction.
155	/// Note that `Endofunction` composition is reversed relative to standard function composition:
156	/// `append(f, g)` results in `f . g` (read as "f after g"), meaning `g` is applied first, then `f`.
157	///
158	/// ### Type Signature
159	///
160	#[hm_signature(Semigroup)]
161	///
162	/// ### Parameters
163	///
164	#[doc_params(
165		"The second function to apply (the outer function).",
166		"The first function to apply (the inner function)."
167	)]
168	///
169	/// ### Returns
170	///
171	/// The composed function `a . b`.
172	///
173	/// ### Examples
174	///
175	/// ```
176	/// use fp_library::{brands::*, functions::*, types::*};
177	///
178	/// let f = Endofunction::<RcFnBrand, _>::new(cloneable_fn_new::<RcFnBrand, _, _>(|x: i32| x * 2));
179	/// let g = Endofunction::<RcFnBrand, _>::new(cloneable_fn_new::<RcFnBrand, _, _>(|x: i32| x + 1));
180	///
181	/// // f(g(x)) = (x + 1) * 2
182	/// let h = append::<_>(f, g);
183	/// assert_eq!(h.0(5), 12);
184	/// ```
185	fn append(
186		a: Self,
187		b: Self,
188	) -> Self {
189		let f = a.0;
190		let g = b.0;
191		// Compose: f . g
192		Self::new(<FnBrand as CloneableFn>::new(move |x| f(g(x))))
193	}
194}
195
196impl<'a, FnBrand: 'a + CloneableFn, A: 'a> Monoid for Endofunction<'a, FnBrand, A> {
197	/// The identity element.
198	///
199	/// This method returns the identity endofunction, which wraps the identity function.
200	///
201	/// ### Type Signature
202	///
203	#[hm_signature(Monoid)]
204	///
205	/// ### Returns
206	///
207	/// The identity endofunction.
208	///
209	/// ### Examples
210	///
211	/// ```
212	/// use fp_library::{brands::*, functions::*, types::*};
213	///
214	/// let id = empty::<Endofunction<RcFnBrand, i32>>();
215	/// assert_eq!(id.0(5), 5);
216	/// ```
217	fn empty() -> Self {
218		Self::new(<FnBrand as CloneableFn>::new(identity))
219	}
220}
221
222#[cfg(test)]
223mod tests {
224	use super::*;
225	use crate::{
226		brands::RcFnBrand,
227		classes::{cloneable_fn::CloneableFn, monoid::empty, semigroup::append},
228	};
229	use quickcheck_macros::quickcheck;
230
231	// Semigroup Laws
232
233	/// Tests the associativity law for Semigroup.
234	#[quickcheck]
235	fn semigroup_associativity(val: i32) -> bool {
236		let f = Endofunction::<RcFnBrand, _>::new(<RcFnBrand as CloneableFn>::new(|x: i32| {
237			x.wrapping_add(1)
238		}));
239		let g = Endofunction::<RcFnBrand, _>::new(<RcFnBrand as CloneableFn>::new(|x: i32| {
240			x.wrapping_mul(2)
241		}));
242		let h = Endofunction::<RcFnBrand, _>::new(<RcFnBrand as CloneableFn>::new(|x: i32| {
243			x.wrapping_sub(3)
244		}));
245
246		let lhs = append(f.clone(), append(g.clone(), h.clone()));
247		let rhs = append(append(f, g), h);
248
249		lhs.0(val) == rhs.0(val)
250	}
251
252	// Monoid Laws
253
254	/// Tests the left identity law for Monoid.
255	#[quickcheck]
256	fn monoid_left_identity(val: i32) -> bool {
257		let f = Endofunction::<RcFnBrand, _>::new(<RcFnBrand as CloneableFn>::new(|x: i32| {
258			x.wrapping_add(1)
259		}));
260		let id = empty::<Endofunction<RcFnBrand, i32>>();
261
262		let res = append(id, f.clone());
263		res.0(val) == f.0(val)
264	}
265
266	/// Tests the right identity law for Monoid.
267	#[quickcheck]
268	fn monoid_right_identity(val: i32) -> bool {
269		let f = Endofunction::<RcFnBrand, _>::new(<RcFnBrand as CloneableFn>::new(|x: i32| {
270			x.wrapping_add(1)
271		}));
272		let id = empty::<Endofunction<RcFnBrand, i32>>();
273
274		let res = append(f.clone(), id);
275		res.0(val) == f.0(val)
276	}
277}
fp_library/types/endofunction.rs

fp_library/types/
endofunction.rs
