free_algebra/specifics/
free_pow.rs

1use super::*;
2
3///
4///The free multiplication of members of type `C` raised to some power
5///
6///The primary use-case of this is to compress the storage requirements of a [FreeGroup] or [FreeMonoid]
7///by grouping repeated elements with an [integral](IntegerSubset) exponent, but other, more exotic,
8///exponents are supported as well
9///
10///# Examples
11///```
12///use free_algebra::{FreePowMonoid, FreePow};
13///
14///let x = FreePow('a', 1) * FreePow('a', 2) * FreePow('b', 1) * FreePow('a', 2);
15///let y = FreePow('a', -2) * FreePow('b', 1);
16///
17///assert_eq!(x, [FreePow('a', 3), FreePow('b', 1), FreePow('a', 2)]);
18///assert_eq!(y, [FreePow('a', -2), FreePow('b', 1)]);
19///assert_eq!(x*y, [FreePow('a', 3), FreePow('b', 2)]);
20///
21///```
22///
23///
24pub type FreePowMonoid<C,P> = MonoidalString<FreePow<C,P>,PowRule>;
25
26///
27///Represents a free symbol raised to some power
28///
29///This is used in [FreePowMonoid] mainly as a way to compress the size-footprint of a
30///[FreeMonoid] by combining repeated elements under an integral exponent, but the option for more
31///exotic exponents is also available
32///
33#[derive(Derivative)]
34#[derivative(PartialEq, Eq, Clone, Copy, Hash, Debug)]
35pub struct FreePow<C:Eq,P>(pub C,pub P);
36
37impl<C:Eq+Display,P:Display> Display for FreePow<C,P> {
38    fn fmt(&self, f: &mut Formatter) -> ::std::fmt::Result {
39        write!(f, "{}^{}", self.0, self.1)
40    }
41}
42
43impl<C:Eq,P:One+Neg<Output=P>> From<FreeInv<C>> for FreePow<C,P> {
44    fn from(inv: FreeInv<C>) -> Self {
45        match inv {
46            FreeInv::Id(x) => FreePow(x,P::one()),
47            FreeInv::Inv(x) => FreePow(x,-P::one()),
48        }
49    }
50}
51
52///Multiplication between [FreePow] elements using addition of exponents on equal bases
53pub struct PowRule;
54
55impl<C:Eq,P:Add<Output=P>+AddAssociative> AssociativeMonoidRule<FreePow<C,P>> for PowRule {}
56impl<C:Eq,P:Add<Output=P>> MonoidRule<FreePow<C,P>> for PowRule {
57    fn apply(mut string: Vec<FreePow<C,P>>, letter: FreePow<C,P>) -> Vec<FreePow<C,P>> {
58        if string.last().map_or(false, |l| l.0==letter.0) {
59            let last = string.pop().unwrap();
60            let last = FreePow(letter.0, last.1 + letter.1);
61            if !last.1._is_zero() { string.push(last); }
62        } else {
63            string.push(letter);
64        }
65        string
66    }
67}
68
69impl<C:Eq,P:Add<Output=P>+Neg<Output=P>+Zero> InvMonoidRule<FreePow<C,P>> for PowRule {
70    fn invert(free: FreePow<C,P>) -> FreePow<C,P> { free.inv() }
71}
72
73impl<C:Eq,P:One> From<C> for FreePow<C,P> { fn from(c:C) -> Self { (c,P::one()).into() } }
74impl<C:Eq,P> From<(C,P)> for FreePow<C,P> { fn from((c,z):(C,P)) -> Self { FreePow(c,z) } }
75
76impl<C:Eq,P:Neg<Output=P>> Inv for FreePow<C,P> {
77    type Output = Self;
78    fn inv(self) -> Self { FreePow(self.0, -self.1) }
79}
80
81impl<C:Eq,P:Mul<Output=P>> Pow<P> for FreePow<C,P> {
82    type Output = FreePow<C,P>;
83    fn pow(self, rhs:P) -> FreePow<C,P> { FreePow(self.0, self.1 * rhs) }
84}
85
86impl<C:Eq,P:Add<Output=P>> Mul for FreePow<C,P> {
87    type Output = FreePowMonoid<C,P>;
88    fn mul(self, rhs:Self) -> FreePowMonoid<C,P> { FreePowMonoid::from(self) * rhs }
89}
90
91impl<C:Eq,P:Add<Output=P>+One> Mul<C> for FreePow<C,P> {
92    type Output = FreePowMonoid<C,P>;
93    fn mul(self, rhs:C) -> FreePowMonoid<C,P> { self * Self::from(rhs) }
94}
95
96impl<C:Eq,P:Add<Output=P>> Mul<FreePowMonoid<C,P>> for FreePow<C,P> {
97    type Output = FreePowMonoid<C,P>;
98    fn mul(self, rhs:FreePowMonoid<C,P>) -> FreePowMonoid<C,P> { FreePowMonoid::from(self) * rhs }
99}
100
101impl<C:Eq,P:Add<Output=P>+Neg<Output=P>+Zero> Div for FreePow<C,P> {
102    type Output = FreePowMonoid<C,P>;
103    fn div(self, rhs:Self) -> FreePowMonoid<C,P> { self * rhs.inv() }
104}
105
106impl<C:Eq,P:Add<Output=P>+One+Neg<Output=P>+Zero> Div<C> for FreePow<C,P> {
107    type Output = FreePowMonoid<C,P>;
108    fn div(self, rhs:C) -> FreePowMonoid<C,P> { self / Self::from(rhs) }
109}
110
111impl<C:Eq,P:Add<Output=P>+Neg<Output=P>+Zero> Div<FreePowMonoid<C,P>> for FreePow<C,P> {
112    type Output = FreePowMonoid<C,P>;
113    fn div(self, rhs:FreePowMonoid<C,P>) -> FreePowMonoid<C,P> { FreePowMonoid::from(self) / rhs }
114}
free_algebra/specifics/free_pow.rs

free_algebra/specifics/
free_pow.rs
