free_algebra/specifics/
free_group.rs

1use super::*;
2
3///
4///A [FreeMonoid], but where each letter can be inverted
5///
6///In essence, this entails constructing a [FreeMonoid] over [FreeInv<C>](FreeInv) with the same
7///multiplication _except_ that elements cancel with their inverses
8///
9///# Examples
10///```
11///use maths_traits::algebra::{One, Inv};
12///use free_algebra::FreeGroup;
13///
14///use free_algebra::FreeInv::*;
15///
16///let x = Id('a') * Id('b').inv() * Id('c');
17///let y = (&x).inv();
18///
19///assert_eq!(x, [Id('a'), Inv('b'), Id('c')]);
20///assert_eq!(y, [Inv('c'), Id('b'), Inv('a')]);
21///assert!((&x / &x).is_one());
22///assert!((&y * &x).is_one());
23///assert!((&x * &y).is_one());
24///
25///let mul = &x * Id('d') * (&y);
26///assert_eq!(mul, [Id('a'), Inv('b'), Id('c'), Id('d'), Inv('c'), Id('b'), Inv('a')]);
27///
28///```
29///
30pub type FreeGroup<C> = MonoidalString<FreeInv<C>,InvRule>;
31
32///
33///Wraps a type `T` and symbolically inverts elements.
34///
35///Used for constructing [FreeGroup]
36///
37#[derive(Clone, Copy, PartialEq, Eq, Hash, Debug)]
38pub enum FreeInv<T:Eq> {
39    ///Wraps an instance of type `T`
40    Id(T),
41    ///The symbolic inverse of an object of type `T`
42    Inv(T)
43}
44
45impl<T:Eq> From<T> for FreeInv<T> {
46    fn from(t:T) -> Self { FreeInv::Id(t) }
47}
48
49///
50///Provides a reference to this type's inner `T`
51///
52///Note that this does not convey any information regarding the state of inversion
53///
54impl<T:Eq> AsRef<T> for FreeInv<T> {
55    fn as_ref(&self) -> &T {
56        match self {
57            FreeInv::Id(ref x) => x,
58            FreeInv::Inv(ref x) => x
59        }
60    }
61}
62
63///
64///Provides a mutable reference to this type's inner `T`
65///
66///Note that this does not convey any information regarding the state of inversion
67///
68impl<T:Eq> AsMut<T> for FreeInv<T> {
69    fn as_mut(&mut self) -> &mut T {
70        match self {
71            FreeInv::Id(ref mut x) => x,
72            FreeInv::Inv(ref mut x) => x
73        }
74    }
75}
76
77impl<T:Eq> PartialEq<T> for FreeInv<T> {
78    fn eq(&self, rhs:&T) -> bool {
79        match self {
80            FreeInv::Id(x) => x==rhs,
81            FreeInv::Inv(_) => false
82        }
83    }
84}
85
86impl<T:Eq+Display> Display for FreeInv<T> {
87    fn fmt(&self, f: &mut Formatter) -> ::std::fmt::Result {
88        match self {
89            Self::Id(x) => write!(f, "{}", x),
90            Self::Inv(x) => write!(f, "{}⁻¹", x),
91        }
92    }
93}
94
95impl<T:Eq> FreeInv<T> {
96
97    ///
98    ///Returns true if `self` is [inverted](FreeInv::Inv)
99    ///
100    ///```
101    ///use free_algebra::FreeInv::*;
102    ///
103    ///assert!(Inv('a').is_inv());
104    ///assert!(!Id('a').is_inv());
105    ///```
106    ///
107    pub fn is_inv(&self) -> bool {
108        match self { Self::Inv(_) => true, _ => false }
109    }
110
111    ///
112    ///Returns true if `self` is [non-inverted](FreeInv::Inv)
113    ///
114    ///```
115    ///use free_algebra::FreeInv::*;
116    ///
117    ///assert!(Id('a').is_id());
118    ///assert!(!Inv('a').is_id());
119    ///```
120    ///
121    pub fn is_id(&self) -> bool {
122        match self { Self::Id(_) => true, _ => false }
123    }
124
125    ///Determines if two objects are inverses
126    fn are_inverses(&self, rhs:&Self) -> bool {
127        self.as_ref()==rhs.as_ref() && self.is_inv()^rhs.is_inv()
128    }
129}
130
131///Multiplication of [FreeInv] elements using concatenation with inverse cancellation
132pub struct InvRule;
133
134impl<T:Eq> AssociativeMonoidRule<FreeInv<T>> for InvRule {}
135impl<T:Eq> MonoidRule<FreeInv<T>> for InvRule {
136    fn apply(mut string: Vec<FreeInv<T>>, letter: FreeInv<T>) -> Vec<FreeInv<T>> {
137        if string.last().map_or(false, |last| letter.are_inverses(last)) {
138            string.pop();
139        } else {
140            string.push(letter);
141        }
142        string
143    }
144}
145
146impl<T:Eq> InvMonoidRule<FreeInv<T>> for InvRule {
147    fn invert(letter: FreeInv<T>) -> FreeInv<T> { letter.inv() }
148}
149
150impl<T:Eq> Inv for FreeInv<T> {
151    type Output = Self;
152    fn inv(self) -> Self {
153        match self {
154            Self::Id(x) => Self::Inv(x),
155            Self::Inv(x) => Self::Id(x)
156        }
157    }
158}
159
160impl<T:Eq> Mul for FreeInv<T> {
161    type Output = FreeGroup<T>;
162    fn mul(self, rhs:Self) -> FreeGroup<T> { FreeGroup::from(self) * rhs }
163}
164
165impl<T:Eq> Div for FreeInv<T> {
166    type Output = FreeGroup<T>;
167    fn div(self, rhs:Self) -> FreeGroup<T> { self * rhs.inv() }
168}
169
170impl<T:Eq> Mul<FreeGroup<T>> for FreeInv<T> {
171    type Output = FreeGroup<T>;
172    fn mul(self, rhs:FreeGroup<T>) -> FreeGroup<T> { FreeGroup::from(self) * rhs }
173}
174
175impl<T:Eq> Div<FreeGroup<T>> for FreeInv<T> {
176    type Output = FreeGroup<T>;
177    fn div(self, rhs:FreeGroup<T>) -> FreeGroup<T> { FreeGroup::from(self) / rhs }
178}
free_algebra/specifics/free_group.rs

free_algebra/specifics/
free_group.rs
