amonoid 0.1.2

//! # [Monoid homomorphisms](https://en.wikipedia.org/wiki/Monoid#Monoid_homomorphisms)
//! A monoid homomorphism is a map (function) (here `f`) from a monoid (here `M1`) to a monoid (here `M2`),
//! that fulfills the following conditions:
//! - `f(M1::ident()) == M2::ident()`,
//! - `f(M1::combine(a, b)) == M2::combine(self.call(a), self.call(b))` for all `a, b: M1`,
//! - Due to the definition of [`trait Monoid`](crate::Monoid), we have an additional condition:
//!    ```text
//!    f(M1::combine_iter(iter)) == M2::combine_iter(iter.map(f))
//!    ```
//!    for all iterators `iter: I: Iterator<Item = M1>`.
//!    (This is follows from the previous condition if both `M1` and `M2` use the default impl for `combine_iter`)
//!
//! ## Flavors
//! Since Rust's functions come in three flavors ([`FnOnce`], [`Fn`] and [`FnMut`]),
//! this module mimics that with [`HomOnce`], [`Hom`] and [`HomMut`],
//! although the first one doesn't make too much sense given that you can't call it multiple times
//! (see its docs for more details).
//!
//! Additionally, there is [`HomStatic`] that works somewhat like a function
//! in that you only need its type to call it.
//!
//! All of these also come in `Borrowed` variants, that take a reference to a [`PreMonoidBorrowed`] instead.

use std::borrow::{Borrow, Cow};
use std::marker::PhantomData;
use std::ops::{Deref, DerefMut};

use self::graph::Graph;
use crate::borrowed::PreMonoidBorrowed;
use crate::list::{List, ListBorrowed};
use crate::{Monoid, MonoidBorrowed};

/// An [`FnOnce`]-like monoid homomorphism (see the [module-level documentation](self) for details).
///
/// This doesn't make too much sense on the face of it,
/// since the second and third conditions to a monoid homomorphism require calling the function multiple times,
/// but that can be somewhat resolved by thinking about this as a _handle_ to a function that,
/// if you could call it multiple times, would actually be a monoid homomorphism,
/// but the version you happen to have is just restricted to one call only.
#[allow(missing_docs)]
pub trait HomOnce<M: Monoid> {
	type Output: Monoid;

	fn call_once(self, m: M) -> Self::Output;
}

/// An [`FnMut`]-like monoid homomorphism (see the [module-level documentation](self) for details).
#[allow(missing_docs)]
pub trait HomMut<M: Monoid>: HomOnce<M> {
	fn call_mut(&mut self, m: M) -> Self::Output;
}

/// An [`Fn`]-like monoid homomorphism (see the [module-level documentation](self) for details).
#[allow(missing_docs)]
pub trait Hom<M: Monoid>: HomMut<M> {
	fn call(&self, m: M) -> Self::Output;
}

/// A function-like monoid homomorphism (see the [module-level documentation](self) for details).
#[allow(missing_docs)]
pub trait HomStatic<M: Monoid>: Hom<M> {
	fn call_static(m: M) -> Self::Output;
}

/// A monoid consisting of an input monoid value and the output of a homomorphism at that value.
pub mod graph {
	use super::*;
	/// The graph type of a monoid homomorphism, i.e. a value of type `M` and the output of `H` for that value.
	pub struct Graph<M: PreMonoidBorrowed, H: HomStaticBorrowed<M>> {
		pub(super) input: M,
		pub(super) output: H::Output,
		#[cfg(feature = "graph-track-inconsistency")]
		possibly_inconsistent: bool,
	}

	impl<M: PreMonoidBorrowed + Clone, H: HomStaticBorrowed<M>> Clone for Graph<M, H>
	where
		H::Output: Clone,
	{
		fn clone(&self) -> Self {
			Self {
				input: self.input.clone(),
				output: self.output.clone(),
				#[cfg(feature = "graph-track-inconsistency")]
				possibly_inconsistent: self.possibly_inconsistent,
			}
		}
	}

	// NOTE: Graph isn't a PreMonoidBorrowed because of the `output` field.
	impl<M: Monoid, H: HomStaticBorrowed<M>> Monoid for Graph<M, H> {
		fn ident() -> Self {
			Self {
				input: M::ident(),
				output: H::Output::ident(),
				#[cfg(feature = "graph-track-inconsistency")]
				possibly_inconsistent: false,
			}
		}

		fn combine(self, rhs: Self) -> Self {
			Self {
				input: self.input.combine(rhs.input),
				output: self.output.combine(rhs.output),
				#[cfg(feature = "graph-track-inconsistency")]
				possibly_inconsistent: self.possibly_inconsistent || rhs.possibly_inconsistent,
			}
		}

		fn combine_assign(&mut self, rhs: Self) {
			self.input.combine_assign(rhs.input);
			self.output.combine_assign(rhs.output);
			#[cfg(feature = "graph-track-inconsistency")]
			{
				self.possibly_inconsistent |= rhs.possibly_inconsistent;
			}
		}

		fn combine_assign_to(self, rhs: &mut Self) {
			self.input.combine_assign_to(&mut rhs.input);
			self.output.combine_assign_to(&mut rhs.output);
			#[cfg(feature = "graph-track-inconsistency")]
			{
				rhs.possibly_inconsistent |= self.possibly_inconsistent;
			}
		}
	}

	impl<M: PreMonoidBorrowed, H: HomStaticBorrowed<M>> Graph<M, H> {
		/// Construct a `Graph` value based on the input value.
		pub fn new(input: M) -> Self {
			Self {
				output: H::call_static_borrowed(&input),
				input,
				#[cfg(feature = "graph-track-inconsistency")]
				possibly_inconsistent: false,
			}
		}

		/// Consume `self` to obtain the input and output by value,
		pub fn into_pair(self) -> (M, H::Output) {
			(self.input, self.output)
		}

		/// Get the input value.
		pub fn input(&self) -> &M {
			&self.input
		}

		/// Get the input value mutably.
		///
		/// This requires a special wrapper to recalculate the output value at the end of the borrow.
		/// Doing that is necessary since this method can't know whether the input has actually been changed,
		/// so it has to assume that it has.
		///
		/// # Edge Case Inconsistency
		/// When the returned [`GraphInputRefMut`] goes out of scope without running its destructor
		/// (e.g. via [`std::mem::forget`]),
		/// this will leave `self` in an inconsistent state if the input has been modified.
		///
		/// To correct this, you can use the [`recalculate_output`](Self::recalculate_output) method.
		/// To check whether you need to do that, you
		#[cfg_attr(
			feature = "graph-track-inconsistency",
			doc = "can use the [`possibly_inconsistent`](Self::possibly_inconsistent) method."
		)]
		#[cfg_attr(
			not(feature = "graph-track-inconsistency"),
			doc = "may want to enable the `graph-track-inconsistency` crate feature
				to gain access to the `possibly_inconsistent` method."
		)]
		pub fn input_mut(&mut self) -> GraphInputRefMut<M, H> {
			#[cfg(feature = "graph-track-inconsistency")]
			{
				self.possibly_inconsistent = true;
			}
			GraphInputRefMut(self)
		}

		/// Whether a [`GraphInputRefMut`] to `self` has gone out of scope without running its destructor.
		///
		/// See [`input_mut`](Self::input_mut) for a more thorough explanation.
		#[cfg(feature = "graph-track-inconsistency")]
		pub fn possibly_inconsistent(&self) -> bool {
			// When this method is called, the borrowing rules make sure that
			// `self` can't also be borrowed inside a `GraphInputRefMut`.
			// (You might argue that `self` could actually be the same reference from inside a `GraphInputRefMut`,
			// but that is prevented by privacy, i.e. there's no public way to call this function from there.)
			// Thus, `self.possibly_inconsistent` being `false` here
			// can only happen if a `GraphInputRefMut` to `self` wasn't dropped properly.
			self.possibly_inconsistent
		}

		/// Recalculate the output from the input.
		///
		/// This is only necessary in the edge case of [`input_mut`](Self::input_mut).
		pub fn recalculate_output(&mut self) {
			self.output = H::call_static_borrowed(&self.input);
			#[cfg(feature = "graph-track-inconsistency")]
			{
				self.possibly_inconsistent = false;
			}
		}

		/// Get the output value.
		pub fn output(&self) -> &H::Output {
			&self.output
		}
	}

	/// A wrapper that acts as a `&mut M`, but recalculates the associated output value when going out of scope.
	pub struct GraphInputRefMut<'a, M: PreMonoidBorrowed, H: HomStaticBorrowed<M>>(
		&'a mut Graph<M, H>,
	);

	impl<M: PreMonoidBorrowed, H: HomStaticBorrowed<M>> Deref for GraphInputRefMut<'_, M, H> {
		type Target = M;

		fn deref(&self) -> &Self::Target {
			&self.0.input
		}
	}

	impl<M: PreMonoidBorrowed, H: HomStaticBorrowed<M>> DerefMut for GraphInputRefMut<'_, M, H> {
		fn deref_mut(&mut self) -> &mut M {
			&mut self.0.input
		}
	}

	impl<M: PreMonoidBorrowed, H: HomStaticBorrowed<M>> Drop for GraphInputRefMut<'_, M, H> {
		fn drop(&mut self) {
			self.0.recalculate_output();
		}
	}
}

/// Like [`HomOnce`], but for [`PreMonoidBorrowed`].
#[allow(missing_docs)]
pub trait HomOnceBorrowed<M: ?Sized + PreMonoidBorrowed> {
	type Output: Monoid;

	fn call_once_borrowed(self, m: &M) -> Self::Output;
}
/// Like [`HomMut`], but for [`PreMonoidBorrowed`].
#[allow(missing_docs)]
pub trait HomMutBorrowed<M: ?Sized + PreMonoidBorrowed>: HomOnceBorrowed<M> {
	fn call_mut_borrowed(&mut self, m: &M) -> Self::Output;
}
/// Like [`Hom`], but for [`PreMonoidBorrowed`].
#[allow(missing_docs)]
pub trait HomBorrowed<M: ?Sized + PreMonoidBorrowed>: HomMutBorrowed<M> {
	fn call_borrowed(&self, m: &M) -> Self::Output;
}
/// Like [`HomStatic`], but for [`PreMonoidBorrowed`].
#[allow(missing_docs)]
pub trait HomStaticBorrowed<M: ?Sized + PreMonoidBorrowed>: HomBorrowed<M> {
	fn call_static_borrowed(m: &M) -> Self::Output;
}

/// A helper macro that implements all lower tiers of `Hom*` for you,
/// so you don't have to repeat yourself so much when implementing [`HomMut`], [`Hom`], or [`HomStatic`].
#[macro_export]
macro_rules! impl_all_monoid_hom {
	// Yes, this is a whole mess of copy-paste spaghetti, but doing it like this is quick and easy.
	($(#[doc = $($doc:tt)*])*
	impl$([$($gen:tt)*])? HomMut for $T:ty
	$(where [$($where:tt)*])? {
		$(#[$attr:meta])*
		fn call_mut(&mut $self:ident, $m:ident: $inp:ty) -> $O:ty $body:block
	}) => {
		$(#[doc = $($doc)*])*
		impl$(<$($gen)*>)? $crate::hom::HomOnce<$inp> for $T
		$(where $($where)*)? {
			type Output = $O;

			#[inline]
			fn call_once(mut self, $m: $inp) -> $O {
				$crate::hom::HomMut::call_mut(&mut self, $m)
			}
		}
		$(#[doc = $($doc)*])*
		impl$(<$($gen)*>)? $crate::hom::HomMut<$inp> for $T
		$(where $($where)*)? {
			$(#[$attr])*
			fn call_mut(&mut $self, $m: $inp) -> $O $body
		}
	};
	($(#[doc = $($doc:tt)*])*
	impl$([$($gen:tt)*])? Hom for $T:ty
	$(where [$($where:tt)*])? {
		$(#[$attr:meta])*
		fn call(&$self:ident, $m:ident: $inp:ty) -> $O:ty $body:block
	}) => {
		$(#[doc = $($doc)*])*
		impl$(<$($gen)*>)? $crate::hom::HomOnce<$inp> for $T
		$(where $($where)*)? {
			type Output = $O;

			#[inline]
			fn call_once(self, $m: $inp) -> $O {
				$crate::hom::Hom::call(&self, $m)
			}
		}
		$(#[doc = $($doc)*])*
		impl$(<$($gen)*>)? $crate::hom::HomMut<$inp> for $T
		$(where $($where)*)? {
			#[inline]
			fn call_mut(&mut self, $m: $inp) -> $O {
				$crate::hom::Hom::call(&*self, $m)
			}
		}
		$(#[doc = $($doc)*])*
		impl$(<$($gen)*>)? $crate::hom::Hom<$inp> for $T
		$(where $($where)*)? {
			$(#[$attr])*
			fn call(&$self, $m: $inp) -> $O $body
		}
	};
	($(#[doc = $($doc:tt)*])*
	impl$([$($gen:tt)*])? HomStatic for $T:ty
	$(where [$($where:tt)*])? {
		$(#[$attr:meta])*
		fn call_static($m:ident: $inp:ty) -> $O:ty $body:block
	}) => {
		$(#[doc = $($doc)*])*
		impl$(<$($gen)*>)? $crate::hom::HomOnce<$inp> for $T
		$(where $($where)*)? {
			type Output = $O;

			#[inline]
			fn call_once(self, $m: $inp) -> $O {
				<Self as $crate::hom::HomStatic<$inp>>::call_static($m)
			}
		}
		$(#[doc = $($doc)*])*
		impl$(<$($gen)*>)? $crate::hom::HomMut<$inp> for $T
		$(where $($where)*)? {
			#[inline]
			fn call_mut(&mut self, $m: $inp) -> $O {
				<Self as $crate::hom::HomStatic<$inp>>::call_static($m)
			}
		}
		$(#[doc = $($doc)*])*
		impl$(<$($gen)*>)? $crate::hom::Hom<$inp> for $T
		$(where $($where)*)? {
			#[inline]
			fn call(&self, $m: $inp) -> $O {
				<Self as $crate::hom::HomStatic<$inp>>::call_static($m)
			}
		}
		$(#[doc = $($doc)*])*
		impl$(<$($gen)*>)? $crate::hom::HomStatic<$inp> for $T
		$(where $($where)*)? {
			$(#[$attr])*
			fn call_static($m: $inp) -> $O $body
		}
	};
	($(#[doc = $($doc:tt)*])*
	impl$([$($gen:tt)*])? HomMutBorrowed for $T:ty
	$(where [$($where:tt)*])? {
		$(#[$attr:meta])*
		fn call_mut_borrowed(&mut $self:ident, $m:ident: &$inp:ty) -> $O:ty $body:block
	}) => {
		$(#[doc = $($doc)*])*
		impl$(<$($gen)*>)? $crate::hom::HomOnceBorrowed<$inp> for $T
		$(where $($where)*)? {
			type Output = $O;

			#[inline]
			fn call_once_borrowed(mut self, $m: &$inp) -> $O {
				$crate::hom::HomMutBorrowed::call_mut_borrowed(&mut self, $m)
			}
		}
		$(#[doc = $($doc)*])*
		impl$(<$($gen)*>)? $crate::hom::HomMutBorrowed<$inp> for $T
		$(where $($where)*)? {
			$(#[$attr])*
			fn call_mut_borrowed(&mut $self, $m: &$inp) -> $O $body
		}
	};
	($(#[doc = $($doc:tt)*])*
	impl$([$($gen:tt)*])? HomBorrowed for $T:ty
	$(where [$($where:tt)*])? {
		$(#[$attr:meta])*
		fn call_borrowed(&$self:ident, $m:ident: &$inp:ty) -> $O:ty $body:block
	}) => {
		$(#[doc = $($doc)*])*
		impl$(<$($gen)*>)? $crate::hom::HomOnceBorrowed<$inp> for $T
		$(where $($where)*)? {
			type Output = $O;

			#[inline]
			fn call_once_borrowed(self, $m: &$inp) -> $O {
				$crate::hom::HomBorrowed::call_borrowed(&self, $m)
			}
		}
		$(#[doc = $($doc)*])*
		impl$(<$($gen)*>)? $crate::hom::HomMutBorrowed<$inp> for $T
		$(where $($where)*)? {
			#[inline]
			fn call_mut_borrowed(&mut self, $m: &$inp) -> $O {
				$crate::hom::HomBorrowed::call_borrowed(&*self, $m)
			}
		}
		$(#[doc = $($doc)*])*
		impl$(<$($gen)*>)? $crate::hom::HomBorrowed<$inp> for $T
		$(where $($where)*)? {
			$(#[$attr])*
			fn call_borrowed(&$self, $m: &$inp) -> $O $body
		}
	};
	($(#[doc = $($doc:tt)*])*
	impl$([$($gen:tt)*])? HomStaticBorrowed for $T:ty
	$(where [$($where:tt)*])? {
		$(#[$attr:meta])*
		fn call_static_borrowed($m:ident: &$inp:ty) -> $O:ty $body:block
	}) => {
		$(#[doc = $($doc)*])*
		impl$(<$($gen)*>)? $crate::hom::HomOnceBorrowed<$inp> for $T
		$(where $($where)*)? {
			type Output = $O;

			#[inline]
			fn call_once_borrowed(self, $m: &$inp) -> $O {
				<Self as $crate::hom::HomStaticBorrowed<$inp>>::call_static_borrowed($m)
			}
		}
		$(#[doc = $($doc)*])*
		impl$(<$($gen)*>)? $crate::hom::HomMutBorrowed<$inp> for $T
		$(where $($where)*)? {
			#[inline]
			fn call_mut_borrowed(&mut self, $m: &$inp) -> $O {
				<Self as $crate::hom::HomStaticBorrowed<$inp>>::call_static_borrowed($m)
			}
		}
		$(#[doc = $($doc)*])*
		impl$(<$($gen)*>)? $crate::hom::HomBorrowed<$inp> for $T
		$(where $($where)*)? {
			#[inline]
			fn call_borrowed(&self, $m: &$inp) -> $O {
				<Self as $crate::hom::HomStaticBorrowed<$inp>>::call_static_borrowed($m)
			}
		}
		$(#[doc = $($doc)*])*
		impl$(<$($gen)*>)? $crate::hom::HomStaticBorrowed<$inp> for $T
		$(where $($where)*)? {
			$(#[$attr])*
			fn call_static_borrowed($m: &$inp) -> $O $body
		}
	};
}
pub use crate::impl_all_monoid_hom;

impl_all_monoid_hom!(impl['a, M: Monoid, H: HomMut<M>] HomMut for &'a mut H {
	#[inline]
	fn call_mut(&mut self, m: M) -> H::Output {
		(*self).call_mut(m)
	}
});
impl_all_monoid_hom!(impl['a, M: Monoid, H: Hom<M>] Hom for &'a H {
	#[inline]
	fn call(&self, m: M) -> H::Output {
		(*self).call(m)
	}
});

impl_all_monoid_hom!(impl['a, M1: Monoid, M2: Monoid] HomMut for Box<dyn 'a + HomMut<M1, Output = M2>> {
	#[inline]
	fn call_mut(&mut self, m: M1) -> M2 {
		(**self).call_mut(m)
	}
});
impl_all_monoid_hom!(impl['a, M1: Monoid, M2: Monoid] Hom for Box<dyn 'a + Hom<M1, Output = M2>> {
	#[inline]
	fn call(&self, m: M1) -> M2 {
		(**self).call(m)
	}
});

/// The identity function is a monoid homomorphism from a monoid to itself.
///
/// This struct deviates from the mathematical formalism a bit:
/// In math, each monoid has its own identity homomorphism;
/// Instead, this is one struct that expresses all of them at once.
///
/// This is possible because of the way the `Hom*` traits have their arguments as generics,
/// which amounts to allowing function overloading.
/// Math, however, has no such function overloading,
/// which prevents it from formulating all identity morphisms as the same thing
/// (which they arguably are, since their formulas are identical: `f(x) = x`).
#[derive(Default, Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
pub struct Id;

impl_all_monoid_hom!(impl[M: Monoid] HomStatic for Id {
	#[inline]
	fn call_static(m: M) -> M {
		m
	}
});

/// The monoid homomorphism that sends `m: M` to [`combine`](Monoid::combine)`(self.0, m)`
#[derive(Default, Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
pub struct LCombine<M>(pub M);
/// The monoid homomorphism that sends `m: M` to [`combine`](Monoid::combine)`(m, self.0)`
#[derive(Default, Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
pub struct RCombine<M>(pub M);

impl<M: Monoid> HomOnce<M> for LCombine<M> {
	type Output = M;

	#[inline]
	fn call_once(self, m: M) -> Self::Output {
		self.0.combine(m)
	}
}
impl<M: Monoid> HomOnce<M> for RCombine<M> {
	type Output = M;

	#[inline]
	fn call_once(self, m: M) -> Self::Output {
		m.combine(self.0)
	}
}
impl<M: Monoid + Clone> HomMut<M> for LCombine<M> {
	#[inline]
	fn call_mut(&mut self, m: M) -> Self::Output {
		self.0.clone().combine(m)
	}
}
impl<M: Monoid + Clone> HomMut<M> for RCombine<M> {
	#[inline]
	fn call_mut(&mut self, m: M) -> Self::Output {
		m.combine(self.0.clone())
	}
}
impl<M: Monoid + Clone> Hom<M> for LCombine<M> {
	#[inline]
	fn call(&self, m: M) -> Self::Output {
		self.0.clone().combine(m)
	}
}
impl<M: Monoid + Clone> Hom<M> for RCombine<M> {
	#[inline]
	fn call(&self, m: M) -> Self::Output {
		m.combine(self.0.clone())
	}
}

/// The monoid homomorphism that sends `m: M::MonoidOwned` to [`combine_left_borrowed`](MonoidBorrowed::combine_left_borrowed)`(self.0, m)`
#[derive(Debug, PartialEq, Eq, PartialOrd, Ord, Hash)]
pub struct LCombineRef<'a, M: ?Sized>(pub &'a M);
/// The monoid homomorphism that sends `m: M::MonoidOwned` to [`combine_right_borrowed`](MonoidBorrowed::combine_right_borrowed)`(m, self.0)`
#[derive(Debug, PartialEq, Eq, PartialOrd, Ord, Hash)]
pub struct RCombineRef<'a, M: ?Sized>(pub &'a M);

impl<M: ?Sized> Copy for LCombineRef<'_, M> {}
impl<M: ?Sized> Copy for RCombineRef<'_, M> {}
impl<M: ?Sized> Clone for LCombineRef<'_, M> {
	#[inline]
	fn clone(&self) -> Self {
		*self
	}
}
impl<M: ?Sized> Clone for RCombineRef<'_, M> {
	#[inline]
	fn clone(&self) -> Self {
		*self
	}
}

impl_all_monoid_hom!(impl['a, M: ?Sized + MonoidBorrowed] Hom for LCombineRef<'a, M> {
	#[inline]
	fn call(&self, m: M::MonoidOwned) -> M::MonoidOwned {
		self.0.combine_left_borrowed(m)
	}
});
impl_all_monoid_hom!(impl['a, M: ?Sized + MonoidBorrowed] HomBorrowed for LCombineRef<'a, M> {
	#[inline]
	fn call_borrowed(&self, m: &M) -> M::MonoidOwned {
		self.0.combine_borrowed(m)
	}
});
impl_all_monoid_hom!(impl['a, M: ?Sized + MonoidBorrowed] Hom for RCombineRef<'a, M> {
	#[inline]
	fn call(&self, m: M::MonoidOwned) -> M::MonoidOwned {
		M::combine_right_borrowed(m, self.0)
	}
});
impl_all_monoid_hom!(impl['a, M: ?Sized + MonoidBorrowed] HomBorrowed for RCombineRef<'a, M> {
	#[inline]
	fn call_borrowed(&self, m: &M) -> M::MonoidOwned {
		m.combine_borrowed(self.0)
	}
});

/// Function composition in arrow order.
///
/// For two monoid homomorphisms `H₁: M₁ → M₂` and `H₂: M₂ → M₃`,
/// this is a monoid homomorphism `(H₁ ⛓ H₂): M₁ → M₃`.
///
/// This is usually written as `H₂ ∘ H₁`,
/// which has the opposite (here termed "algebraic") order because, as a function,
/// it is given by `(H₂ ∘ H₁)(x) = H₂(H₁(x))`.
/// When thinking about applying functions one after another,
/// this is very confusing tho, hence the arrow order is preferred here.
///
/// If you want to use the algebraic order instead, see [`Compose`].
#[derive(Default, Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
pub struct Chain<H1, H2>(pub H1, pub H2);

/// Function composition in algebraic order (for more details, see [`Chain`]).
pub type Compose<H2, H1> = Chain<H1, H2>;

impl<M1: Monoid, M2: Monoid, M3: Monoid, H1, H2> HomOnce<M1> for Chain<H1, H2>
where
	H1: HomOnce<M1, Output = M2>,
	H2: HomOnce<M2, Output = M3>,
{
	type Output = M3;

	fn call_once(self, m: M1) -> Self::Output {
		self.1.call_once(self.0.call_once(m))
	}
}
impl<M1: Monoid, M2: Monoid, M3: Monoid, H1, H2> HomMut<M1> for Chain<H1, H2>
where
	H1: HomMut<M1, Output = M2>,
	H2: HomMut<M2, Output = M3>,
{
	fn call_mut(&mut self, m: M1) -> Self::Output {
		self.1.call_mut(self.0.call_mut(m))
	}
}
impl<M1: Monoid, M2: Monoid, M3: Monoid, H1, H2> Hom<M1> for Chain<H1, H2>
where
	H1: Hom<M1, Output = M2>,
	H2: Hom<M2, Output = M3>,
{
	fn call(&self, m: M1) -> Self::Output {
		self.1.call(self.0.call(m))
	}
}
impl<M1: Monoid, M2: Monoid, M3: Monoid, H1, H2> HomStatic<M1> for Chain<H1, H2>
where
	H1: HomStatic<M1, Output = M2>,
	H2: HomStatic<M2, Output = M3>,
{
	fn call_static(m: M1) -> Self::Output {
		H2::call_static(H1::call_static(m))
	}
}
impl<M1: ?Sized + PreMonoidBorrowed, M2: Monoid, M3: Monoid, H1, H2> HomOnceBorrowed<M1>
	for Chain<H1, H2>
where
	H1: HomOnceBorrowed<M1, Output = M2>,
	H2: HomOnce<M2, Output = M3>,
{
	type Output = M3;

	fn call_once_borrowed(self, m: &M1) -> Self::Output {
		self.1.call_once(self.0.call_once_borrowed(m))
	}
}
impl<M1: ?Sized + PreMonoidBorrowed, M2: Monoid, M3: Monoid, H1, H2> HomMutBorrowed<M1>
	for Chain<H1, H2>
where
	H1: HomMutBorrowed<M1, Output = M2>,
	H2: HomMut<M2, Output = M3>,
{
	fn call_mut_borrowed(&mut self, m: &M1) -> Self::Output {
		self.1.call_mut(self.0.call_mut_borrowed(m))
	}
}
impl<M1: ?Sized + PreMonoidBorrowed, M2: Monoid, M3: Monoid, H1, H2> HomBorrowed<M1>
	for Chain<H1, H2>
where
	H1: HomBorrowed<M1, Output = M2>,
	H2: Hom<M2, Output = M3>,
{
	fn call_borrowed(&self, m: &M1) -> Self::Output {
		self.1.call(self.0.call_borrowed(m))
	}
}
impl<M1: ?Sized + PreMonoidBorrowed, M2: Monoid, M3: Monoid, H1, H2> HomStaticBorrowed<M1>
	for Chain<H1, H2>
where
	H1: HomStaticBorrowed<M1, Output = M2>,
	H2: HomStatic<M2, Output = M3>,
{
	fn call_static_borrowed(m: &M1) -> Self::Output {
		H2::call_static(H1::call_static_borrowed(m))
	}
}

/// Monoid endomorphisms (homomorphisms where `Output = Input`) are themselves monoids under composition.
impl<'a, M: 'a + Monoid> Monoid for Box<dyn 'a + HomMut<M, Output = M>> {
	fn ident() -> Self {
		Box::new(Id)
	}

	fn combine(self, rhs: Self) -> Self {
		Box::new(Chain(self, rhs))
	}
}
/// Monoid endomorphisms (homomorphisms where `Output = Input`) are themselves monoids under composition.
impl<'a, M: 'a + Monoid> Monoid for Box<dyn 'a + Hom<M, Output = M>> {
	fn ident() -> Self {
		Box::new(Id)
	}

	fn combine(self, rhs: Self) -> Self {
		Box::new(Chain(self, rhs))
	}
}

/// The monoid homomorphism from `()` that returns the identity element.
///
/// (See also: [Initial object (wiki)](https://en.wikipedia.org/wiki/Initial_object))
pub struct GetIdent<M: Monoid>(PhantomData<M>);

impl_all_monoid_hom! {
	impl[M: Monoid] HomStatic for GetIdent<M> {
		#[inline]
		fn call_static(_m: ()) -> M {
			M::ident()
		}
	}
}
impl_all_monoid_hom! {
	impl[M: Monoid] HomStaticBorrowed for GetIdent<M> {
		#[inline]
		fn call_static_borrowed(_m: &()) -> M {
			M::ident()
		}
	}
}

impl_all_monoid_hom! {
	/// While this is a bit of an abuse of typing,
	/// the unit type here stands for the monoid homomorphism that
	/// just maps everything to the only possible output value.
	///
	/// (See also: [Terminal object (wiki)](https://en.wikipedia.org/wiki/Terminal_object))
	impl[M: Monoid] HomStatic for () {
		#[inline]
		fn call_static(_m: M) -> () {}
	}
}
impl_all_monoid_hom! {
	impl[M: PreMonoidBorrowed] HomStaticBorrowed for () {
		#[inline]
		fn call_static_borrowed(_m: &M) -> () {}
	}
}

/// The product of two monoid homomorphisms, which just applies them componentwise.
///
/// This crate chooses to use a tuple of homomorphisms
/// to represent the more common _product_ of two homomorphisms,
/// rather than the more formally correct _tuple_ of two homomorphisms
/// (where both take the same input, which would also clash with Rust's ownership system).
impl<M1: Monoid, M2: Monoid, H1, H2> HomOnce<(M1, M2)> for (H1, H2)
where
	H1: HomOnce<M1>,
	H2: HomOnce<M2>,
{
	type Output = (H1::Output, H2::Output);

	#[inline]
	fn call_once(self, (m1, m2): (M1, M2)) -> Self::Output {
		(self.0.call_once(m1), self.1.call_once(m2))
	}
}
/// See [`HomOnce for (H1, H2)`](HomOnce#impl-HomOnce<(M1,+M2)>-for-(H1,+H2)) for an explanation.
impl<M1: Monoid, M2: Monoid, H1, H2> HomMut<(M1, M2)> for (H1, H2)
where
	H1: HomMut<M1>,
	H2: HomMut<M2>,
{
	#[inline]
	fn call_mut(&mut self, (m1, m2): (M1, M2)) -> Self::Output {
		(self.0.call_mut(m1), self.1.call_mut(m2))
	}
}
/// See [`HomOnce for (H1, H2)`](HomOnce#impl-HomOnce<(M1,+M2)>-for-(H1,+H2)) for an explanation.
impl<M1: Monoid, M2: Monoid, H1, H2> Hom<(M1, M2)> for (H1, H2)
where
	H1: Hom<M1>,
	H2: Hom<M2>,
{
	#[inline]
	fn call(&self, (m1, m2): (M1, M2)) -> Self::Output {
		(self.0.call(m1), self.1.call(m2))
	}
}
/// See [`HomOnce for (H1, H2)`](HomOnce#impl-HomOnce<(M1,+M2)>-for-(H1,+H2)) for an explanation.
impl<M1: Monoid, M2: Monoid, H1, H2> HomStatic<(M1, M2)> for (H1, H2)
where
	H1: HomStatic<M1>,
	H2: HomStatic<M2>,
{
	#[inline]
	fn call_static((m1, m2): (M1, M2)) -> Self::Output {
		(H1::call_static(m1), H2::call_static(m2))
	}
}

/// [`ToOwned::to_owned`](std::borrow::ToOwned::to_owned)
#[derive(Default, Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
pub struct ToOwned;

impl_all_monoid_hom!(impl[M: ?Sized + MonoidBorrowed + std::borrow::ToOwned<Owned = M::MonoidOwned>] HomStaticBorrowed for ToOwned {
	#[inline]
	fn call_static_borrowed(m: &M) -> M::MonoidOwned {
		m.to_owned()
	}
});

/// [`Cow::<'a, M>::Owned`](Cow::Owned)
pub struct CowFromOwned<'a, M>(PhantomData<fn(M::MonoidOwned) -> Cow<'a, M>>)
where
	M: 'a
		+ ?Sized
		+ PreMonoidBorrowed<MonoidOwned: 'a>
		+ std::borrow::ToOwned<Owned = M::MonoidOwned>;

impl_all_monoid_hom!(impl['a, M: 'a + ?Sized + MonoidBorrowed<MonoidOwned: 'a> + std::borrow::ToOwned<Owned = M::MonoidOwned>] HomStatic for CowFromOwned<'a, M> {
	#[inline]
	fn call_static(m: M::MonoidOwned) -> Cow<'a, M> {
		Cow::Owned(m)
	}
});

/// [`Cow::<'a, M>::into_owned`](Cow::into_owned)
#[derive(Default, Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
pub struct CowIntoOwned<'a, M>(PhantomData<fn(Cow<'a, M>) -> M::MonoidOwned>)
where
	M: 'a
		+ ?Sized
		+ PreMonoidBorrowed<MonoidOwned: 'a>
		+ std::borrow::ToOwned<Owned = M::MonoidOwned>;

impl_all_monoid_hom!(impl['a, M: 'a + ?Sized + MonoidBorrowed<MonoidOwned: 'a> + std::borrow::ToOwned<Owned = M::MonoidOwned>] HomStatic for CowIntoOwned<'a, M> {
	#[inline]
	fn call_static(m: Cow<'a, M>) -> M::MonoidOwned {
		m.into_owned()
	}
});

/// [`Graph::input`], composed with [`Clone::clone`]
#[derive(Default, Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
pub struct GraphInputClone;

impl_all_monoid_hom!(impl[M: Monoid, H: HomStaticBorrowed<M>] HomStatic for GraphInputClone
where [M: Clone] {
	#[inline]
	fn call_static(graph: Graph<M, H>) -> M {
		graph.input.clone()
	}
});

/// [`Graph::output`], composed with [`Clone::clone`]
#[derive(Default, Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
pub struct GraphOutputClone;

impl_all_monoid_hom!(impl[M: Monoid, H: HomStaticBorrowed<M>] HomStatic for GraphOutputClone
where [H::Output: Clone] {
	#[inline]
	fn call_static(graph: Graph<M, H>) -> H::Output {
		graph.output.clone()
	}
});

/// Monoid homomorphism `(L: List) -> M` built from a function `L::Item -> M`.
///
/// This is also known as an [adjunction](https://en.wikipedia.org/wiki/Adjoint_functors).
#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
pub struct ListHomFromFn<F>(pub F);

impl_all_monoid_hom!(impl[L: List, M: Monoid, F: FnMut(L::Item) -> M] HomMut for ListHomFromFn<F> {
	fn call_mut(&mut self, v: L) -> M {
		M::combine_iter(v.into_items().map(&mut self.0))
	}
});
impl<L: List, M: Monoid, F: Fn(L::Item) -> M> Hom<L> for ListHomFromFn<F> {
	fn call(&self, v: L) -> M {
		M::combine_iter(v.into_items().map(&self.0))
	}
}

/// Convert between two different list types with the same item type.
#[derive(Default, Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
pub struct ListIsom<L>(PhantomData<fn() -> L>);

impl_all_monoid_hom!(impl[T, L1: List<Item = T>, L2: List<Item = T>] HomStatic for ListIsom<L2> {
	fn call_static(list: L1) -> L2 {
		L2::from_items(list.into_items())
	}
});
impl_all_monoid_hom!(impl[T, L1: ListBorrowed, L2: List<Item = T>] HomStaticBorrowed for ListIsom<L2>
where [T: Clone, L1::MonoidOwned: List<Item = T>]
{
	fn call_static_borrowed(list: &L1) -> L2 {
		L2::from_items(list.items().map(|it| it.borrow().clone()))
	}
});