alga2 0.1.0

A modern abstract-algebra hierarchy for Rust — the successor to alga, powered by batch-impl
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125

//! Extended algebraic structures (bare-core): idempotent semigroups,
//! bounded lattices, euclidean domains, lie algebras, and integer powers —
//! generated by batch-impl.
//!
//! Tuple caps mirror the std tuple-trait ceiling (12 for `Clone`/`PartialOrd`
//! and anything built on them): `Band` has no std-tuple-trait supertraits and
//! runs to 16; `BoundedLattice` (via `Lattice` → `PartialOrd`) and `Power`
//! (via `Clone`) stop at 12.

use batch_impl::batch_trait;

use crate::op::{Additive, Multiplicative};
use crate::tower::{Band, BoundedLattice, EuclideanDomain, LieAlgebra, Monoid, Power};

batch_trait! {
    Band: @trait<Multiplicative> [bool, (<Band<>>,).1..=16];
    Power: @trait[<Additive>,<Multiplicative>] [@num,bool],
        @trait<Additive> (<@trait<>>,).1..=12,
        @trait<Multiplicative> (<@trait<>>,).1..=12;
    BoundedLattice: [@u*,@i*]{
        fn top() -> Self { Self::MAX } fn bottom() -> Self { Self::MIN }
    },
        bool{
        fn top() -> Self { true } fn bottom() -> Self { false }
    },
        (<@trait>,).1..=12 impl{(A@..,)}{
        fn top() -> Self { ( @(@A::top(),).. ) }
        fn bottom() -> Self { ( @(@A::bottom(),).. ) }
    };
    LieAlgebra: @trait<Additive> [@num,bool]{
        fn bracket(&self, _other: &Self) -> Self {<Self as Monoid>::identity() }
    };
    // Euclidean division: `quot_rem` is the same div_euclid/rem_euclid pair
    // for every family; only the norm representation differs (the `@u*` cast
    // vs the `@i*` unsigned-abs — a type reality, not a duplication).
    EuclideanDomain: @trait<Additive, Multiplicative>[
        [@u8..u64, usize]{
        fn quot_rem(&self, divisor: &Self) -> (Self, Self) { (self.div_euclid(*divisor), self.rem_euclid(*divisor)) }
         fn euclidean_norm(&self) -> u128 { *self as u128 }
    },
        u128{
        fn quot_rem(&self, divisor: &Self) -> (Self, Self) { (self.div_euclid(*divisor), self.rem_euclid(*divisor)) }
         fn euclidean_norm(&self) -> u128 { *self }
    },
        [@i8..i64, isize]{
        fn quot_rem(&self, divisor: &Self) -> (Self, Self) { (self.div_euclid(*divisor), self.rem_euclid(*divisor)) }
         fn euclidean_norm(&self) -> u128 { self.unsigned_abs() as u128 }
    },
        i128{
        fn quot_rem(&self, divisor: &Self) -> (Self, Self) { (self.div_euclid(*divisor), self.rem_euclid(*divisor)) }
         fn euclidean_norm(&self) -> u128 { self.unsigned_abs() }
    }];
}

// `StarSemiring` (Kleene star) deliberately has no in-crate inhabitant: its
// canonical carrier is the *boolean semiring* `({0,1}, or, and)` (regular
// languages, graph path problems) — not the two-element field F₂ (xor
// addition), where `1 + 1 = 0` breaks the closure law `1 + a·a* == a*`.

#[cfg(test)]
mod tests {
    use super::*;
    use crate::tower::{BoundedLattice, EuclideanDomain, Power};

    #[test]
    fn powers_via_square_and_multiply() {
        assert_eq!(<u8 as Power<Multiplicative>>::pow(&3, 4), 81);
        assert_eq!(<u8 as Power<Multiplicative>>::pow(&3, 0), 1);
        assert_eq!(<u8 as Power<Additive>>::pow(&3, 4), 12);
        assert_eq!(<(u8, u8) as Power<Multiplicative>>::pow(&(2, 3), 3), (8, 27));
        // arity-12 tuple: Clone (supertrait of Power) caps std at 12.
        let v = (2u16, 2u16, 2u16, 2u16, 2u16, 2u16, 2u16, 2u16, 2u16, 2u16, 2u16, 2u16);
        let p = <(u16, u16, u16, u16, u16, u16, u16, u16, u16, u16, u16, u16) as Power<
            Multiplicative,
        >>::pow(&v, 10);
        assert_eq!(p.0, 1024);
        assert_eq!(p.11, 1024);
    }

    #[test]
    fn band_tuples_to_16() {
        // Band is std-tuple-trait-free: the (bool, ...) 16-tuple inhabits it.
        fn assert_band<T: Band<Multiplicative>>() {}
        assert_band::<(
            bool,
            bool,
            bool,
            bool,
            bool,
            bool,
            bool,
            bool,
            bool,
            bool,
            bool,
            bool,
            bool,
            bool,
            bool,
            bool,
        )>();
    }

    #[test]
    fn euclidean_gcd() {
        assert_eq!(<u32 as EuclideanDomain<Additive, Multiplicative>>::gcd(&12, &18), 6);
        assert_eq!(<u32 as EuclideanDomain<Additive, Multiplicative>>::gcd(&17, &5), 1);
        assert_eq!(<i64 as EuclideanDomain<Additive, Multiplicative>>::gcd(&-12, &18), 6);
        let (q, r) = <i32 as EuclideanDomain<Additive, Multiplicative>>::quot_rem(&17, &5);
        assert_eq!((q, r), (3, 2));
    }

    #[test]
    fn bounded_lattices() {
        assert_eq!(<u8 as BoundedLattice>::top(), u8::MAX);
        assert_eq!(<u8 as BoundedLattice>::bottom(), 0);
        assert!(<bool as BoundedLattice>::top());
        assert!(!<bool as BoundedLattice>::bottom());
        assert_eq!(<(u8, u8) as BoundedLattice>::top(), (u8::MAX, u8::MAX));
        // arity-12 tuple: Lattice's PartialOrd supertrait caps std at 12.
        let v = <(u8, u8, u8, u8, u8, u8, u8, u8, u8, u8, u8, u8) as BoundedLattice>::top();
        assert_eq!(v.0, u8::MAX);
        assert_eq!(v.11, u8::MAX);
    }
}