fp_library/classes/
monoid.rs

1//! Types that have an identity element and an associative binary operation.
2//!
3//! ### Examples
4//!
5//! ```
6//! use fp_library::functions::*;
7//!
8//! let x: String = empty();
9//! assert_eq!(x, "".to_string());
10//! ```
11
12#[fp_macros::document_module]
13mod inner {
14	use {
15		crate::classes::*,
16		fp_macros::*,
17	};
18
19	/// A type class for types that have an identity element and an associative binary operation.
20	///
21	/// ### Laws
22	///
23	/// `Monoid` instances must satisfy the identity laws:
24	/// * Left Identity: `append(empty(), a) = a`.
25	/// * Right Identity: `append(a, empty()) = a`.
26	#[document_examples]
27	///
28	/// Monoid laws for [`String`]:
29	///
30	/// ```
31	/// use fp_library::functions::*;
32	///
33	/// let a = "hello".to_string();
34	///
35	/// // Left Identity: append(empty(), a) = a
36	/// assert_eq!(append(empty::<String>(), a.clone()), a);
37	///
38	/// // Right Identity: append(a, empty()) = a
39	/// assert_eq!(append(a.clone(), empty::<String>()), a);
40	/// ```
41	///
42	/// Monoid laws for [`Vec`]:
43	///
44	/// ```
45	/// use fp_library::functions::*;
46	///
47	/// let a = vec![1, 2, 3];
48	///
49	/// // Left Identity: append(empty(), a) = a
50	/// assert_eq!(append(empty::<Vec<i32>>(), a.clone()), a);
51	///
52	/// // Right Identity: append(a, empty()) = a
53	/// assert_eq!(append(a.clone(), empty::<Vec<i32>>()), a);
54	/// ```
55	pub trait Monoid: Semigroup {
56		/// The identity element.
57		///
58		/// This method returns the identity element of the monoid.
59		#[document_signature]
60		///
61		#[document_returns("The identity element.")]
62		#[document_examples]
63		///
64		/// ```
65		/// use fp_library::functions::*;
66		///
67		/// let x: String = empty();
68		/// assert_eq!(x, "".to_string());
69		/// ```
70		fn empty() -> Self;
71	}
72
73	/// The identity element.
74	///
75	/// Free function version that dispatches to [the type class' associated function][`Monoid::empty`].
76	#[document_signature]
77	///
78	#[document_type_parameters("The type of the monoid.")]
79	///
80	#[document_returns("The identity element.")]
81	#[document_examples]
82	///
83	/// ```
84	/// use fp_library::functions::*;
85	///
86	/// let x: String = empty();
87	/// assert_eq!(x, "".to_string());
88	/// ```
89	pub fn empty<M: Monoid>() -> M {
90		M::empty()
91	}
92
93	/// Appends a value to itself a given number of times.
94	///
95	/// Uses binary exponentiation for O(log n) appends.
96	#[document_signature]
97	///
98	#[document_type_parameters("The monoid type.")]
99	///
100	#[document_parameters("The value to exponentiate.", "The number of times to append.")]
101	///
102	#[document_returns("The value appended to itself `n` times, or `empty()` if `n` is 0.")]
103	#[document_examples]
104	///
105	/// ```
106	/// use fp_library::functions::*;
107	///
108	/// assert_eq!(power("ab".to_string(), 3), "ababab");
109	/// assert_eq!(power("x".to_string(), 0), "");
110	/// assert_eq!(power(vec![1, 2], 2), vec![1, 2, 1, 2]);
111	/// ```
112	pub fn power<M: Monoid + Clone>(
113		a: M,
114		n: usize,
115	) -> M {
116		if n == 0 {
117			M::empty()
118		} else if n == 1 {
119			a
120		} else if n.is_multiple_of(2) {
121			let half = power(a, n / 2);
122			M::append(half.clone(), half)
123		} else {
124			let rest = power(a.clone(), n - 1);
125			M::append(rest, a)
126		}
127	}
128}
129
130pub use inner::*;
fp_library/classes/monoid.rs

fp_library/classes/
monoid.rs
