catlog/zero/
alg.rs

1//! Commutative algebra and polynomials.
2
3use num_traits::{One, Pow, Zero};
4use std::collections::BTreeMap;
5use std::fmt::Display;
6use std::iter::{Product, Sum};
7use std::ops::{Add, AddAssign, Mul, Neg};
8
9use derivative::Derivative;
10
11use super::rig::*;
12
13/// A commutative algebra over a commutative ring.
14pub trait CommAlg: CommRing + Module<Ring = Self::R> {
15    /// The base ring of the algebra.
16    type R: CommRing;
17
18    /** Convert an element of the base ring into an element of the algebra.
19
20    A commutative algebra A over a commutative ring R can be defined as a ring
21    homomorphism from R to A. This method computes that homomorphism.
22     */
23    fn from_scalar(r: Self::R) -> Self {
24        Self::one() * r
25    }
26}
27
28/** A polynomial in several variables.
29
30This data structure is for polynomials in *normal form*: a **polynomial** is a
31formal linear combination of monomials in which no monomial is repeated, and no
32variable is repeated within any monomial. The implementation is indeed a
33[`Combination`] of a [`Monomial`]s. The use of a normal form means that
34polynomial arithmetic automatically performs certain simplifications.
35
36In abstract terms, polynomials with coefficients valued in a [commutative
37ring](super::rig::CommRing) *R* are the free [commutative algebra](CommAlg)
38over *R*.
39 */
40#[derive(Clone, PartialEq, Eq, Derivative)]
41#[derivative(Default(bound = ""))]
42pub struct Polynomial<Var, Coef, Exp>(Combination<Monomial<Var, Exp>, Coef>);
43
44impl<Var, Coef, Exp> Polynomial<Var, Coef, Exp>
45where
46    Var: Ord,
47    Exp: Ord,
48{
49    /// Constructs the generating polynomial corresponding to a variable.
50    pub fn generator(var: Var) -> Self
51    where
52        Coef: One,
53        Exp: One,
54    {
55        Polynomial::from_monomial(Monomial::generator(var))
56    }
57
58    /// Constructs the polynomial corresponding to a monomial.
59    pub fn from_monomial(m: Monomial<Var, Exp>) -> Self
60    where
61        Coef: One,
62    {
63        Polynomial(Combination::generator(m))
64    }
65
66    /// Iterates over the monomials in the polynomial.
67    pub fn monomials(&self) -> impl ExactSizeIterator<Item = &Monomial<Var, Exp>> {
68        self.0.variables()
69    }
70
71    /** Maps the coefficients of the polynomial.
72
73    In the usual situations when the coefficients from commutative rigs and the
74    mapping is a rig homomorphism, this operation is extension of scalars
75    applied to free commutative algebras.
76     */
77    pub fn extend_scalars<NewCoef, F>(self, f: F) -> Polynomial<Var, NewCoef, Exp>
78    where
79        F: FnMut(Coef) -> NewCoef,
80    {
81        Polynomial(self.0.extend_scalars(f))
82    }
83
84    /// Evaluates the polynomial by substituting for the variables.
85    pub fn eval<A, F>(&self, f: F) -> A
86    where
87        A: Clone + Mul<Coef, Output = A> + Pow<Exp, Output = A> + Sum + Product,
88        F: Clone + FnMut(&Var) -> A,
89        Coef: Clone,
90        Exp: Clone,
91    {
92        self.0.eval_with_order(self.monomials().map(|m| m.eval(f.clone())))
93    }
94
95    /** Evaluates the polynomial on a sequence of variable-value pairs.
96
97    This is a convenient way to evaluate the polynomial at a single point but it
98    is not very efficient.
99    */
100    pub fn eval_pairs<A>(&self, pairs: impl IntoIterator<Item = (Var, A)>) -> A
101    where
102        A: Clone + Mul<Coef, Output = A> + Pow<Exp, Output = A> + Sum + Product,
103        Coef: Clone,
104        Exp: Clone,
105    {
106        let map: BTreeMap<Var, A> = pairs.into_iter().collect();
107        self.eval(|var| map.get(var).cloned().unwrap())
108    }
109
110    /** Maps over the variables in the polynomial.
111
112    The mapping need not be injective. This is conceptually equivalent to
113    [evaluating](Polynomial::eval) the polynomial with a map that sends
114    generators to generators but avoids assuming that an arbitrary polynomial
115    can be exponentiated, which is only makes sense when the exponents are
116    nonnegative integers.
117     */
118    pub fn map_variables<NewVar, F>(&self, mut f: F) -> Polynomial<NewVar, Coef, Exp>
119    where
120        Coef: Clone + Add<Output = Coef>,
121        Exp: Clone + Add<Output = Exp>,
122        NewVar: Clone + Ord,
123        F: FnMut(&Var) -> NewVar,
124    {
125        (&self.0)
126            .into_iter()
127            .map(|(coef, m)| (coef.clone(), m.map_variables(|var| f(var))))
128            .collect()
129    }
130}
131
132impl<Var, Coef, Exp> FromIterator<(Coef, Monomial<Var, Exp>)> for Polynomial<Var, Coef, Exp>
133where
134    Var: Ord,
135    Coef: Add<Output = Coef>,
136    Exp: Ord,
137{
138    fn from_iter<T: IntoIterator<Item = (Coef, Monomial<Var, Exp>)>>(iter: T) -> Self {
139        Polynomial(iter.into_iter().collect())
140    }
141}
142
143impl<Var, Coef, Exp> Display for Polynomial<Var, Coef, Exp>
144where
145    Var: Display,
146    Coef: Display + PartialEq + One,
147    Exp: Display + PartialEq + One,
148{
149    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
150        self.0.fmt(f)
151    }
152}
153
154// XXX: Lots of boilerplate to delegate the module structure of `Polynomial` to
155// `Combination` because these traits cannot be derived automatically.
156
157impl<Var, Coef, Exp> AddAssign<(Coef, Monomial<Var, Exp>)> for Polynomial<Var, Coef, Exp>
158where
159    Var: Ord,
160    Coef: Add<Output = Coef>,
161    Exp: Ord,
162{
163    fn add_assign(&mut self, rhs: (Coef, Monomial<Var, Exp>)) {
164        self.0 += rhs;
165    }
166}
167
168impl<Var, Coef, Exp> Add for Polynomial<Var, Coef, Exp>
169where
170    Var: Ord,
171    Coef: Add<Output = Coef>,
172    Exp: Ord,
173{
174    type Output = Self;
175
176    fn add(self, rhs: Self) -> Self::Output {
177        Polynomial(self.0 + rhs.0)
178    }
179}
180
181impl<Var, Coef, Exp> Zero for Polynomial<Var, Coef, Exp>
182where
183    Var: Ord,
184    Coef: Add<Output = Coef>,
185    Exp: Ord,
186{
187    fn zero() -> Self {
188        Polynomial(Combination::zero())
189    }
190
191    fn is_zero(&self) -> bool {
192        self.0.is_zero()
193    }
194}
195
196impl<Var, Coef, Exp> AdditiveMonoid for Polynomial<Var, Coef, Exp>
197where
198    Var: Ord,
199    Coef: AdditiveMonoid,
200    Exp: Ord,
201{
202}
203
204impl<Var, Coef, Exp> Mul<Coef> for Polynomial<Var, Coef, Exp>
205where
206    Var: Ord,
207    Coef: Clone + Default + Mul<Output = Coef>,
208    Exp: Ord,
209{
210    type Output = Self;
211
212    fn mul(self, a: Coef) -> Self::Output {
213        Polynomial(self.0 * a)
214    }
215}
216
217impl<Var, Coef, Exp> RigModule for Polynomial<Var, Coef, Exp>
218where
219    Var: Ord,
220    Coef: Clone + Default + CommRig,
221    Exp: Ord,
222{
223    type Rig = Coef;
224}
225
226impl<Var, Coef, Exp> Neg for Polynomial<Var, Coef, Exp>
227where
228    Var: Ord,
229    Coef: Default + Neg<Output = Coef>,
230    Exp: Ord,
231{
232    type Output = Self;
233
234    fn neg(self) -> Self::Output {
235        Polynomial(self.0.neg())
236    }
237}
238
239impl<Var, Coef, Exp> AbGroup for Polynomial<Var, Coef, Exp>
240where
241    Var: Ord,
242    Coef: Default + AbGroup,
243    Exp: Ord,
244{
245}
246
247impl<Var, Coef, Exp> Module for Polynomial<Var, Coef, Exp>
248where
249    Var: Ord,
250    Coef: Clone + Default + CommRing,
251    Exp: Ord,
252{
253    type Ring = Coef;
254}
255
256/// Multiply polynomials using the distributive law.
257impl<Var, Coef, Exp> Mul for Polynomial<Var, Coef, Exp>
258where
259    Var: Clone + Ord,
260    Coef: Clone + Add<Output = Coef> + Mul<Output = Coef>,
261    Exp: Clone + Ord + Add<Output = Exp>,
262{
263    type Output = Self;
264
265    fn mul(self, rhs: Self) -> Self::Output {
266        // Avoid unnecessary clones by tracking whether we're in the last
267        // iteration of the outer and inner loops.
268        let mut result = Polynomial::zero();
269        let (outer, inner) = (self.0, rhs.0);
270        let mut outer_iter = outer.into_iter();
271        while let Some((a, m)) = outer_iter.next() {
272            if outer_iter.len() == 0 {
273                let mut inner_iter = inner.into_iter();
274                while let Some((b, n)) = inner_iter.next() {
275                    if inner_iter.len() == 0 {
276                        result += (a * b, m * n);
277                        break;
278                    } else {
279                        result += (a.clone() * b, m.clone() * n);
280                    }
281                }
282                break;
283            } else {
284                for (b, n) in &inner {
285                    result += (a.clone() * b.clone(), m.clone() * n.clone());
286                }
287            }
288        }
289        result
290    }
291}
292
293impl<Var, Coef, Exp> One for Polynomial<Var, Coef, Exp>
294where
295    Var: Clone + Ord,
296    Coef: Clone + Add<Output = Coef> + One,
297    Exp: Clone + Ord + Add<Output = Exp>,
298{
299    fn one() -> Self {
300        Polynomial::from_monomial(Default::default())
301    }
302}
303
304impl<Var, Coef, Exp> Monoid for Polynomial<Var, Coef, Exp>
305where
306    Var: Clone + Ord,
307    Coef: Clone + Rig,
308    Exp: Clone + Ord + AdditiveMonoid,
309{
310}
311
312impl<Var, Coef, Exp> Rig for Polynomial<Var, Coef, Exp>
313where
314    Var: Clone + Ord,
315    Coef: Clone + Rig,
316    Exp: Clone + Ord + AdditiveMonoid,
317{
318}
319
320impl<Var, Coef, Exp> Ring for Polynomial<Var, Coef, Exp>
321where
322    Var: Clone + Ord,
323    Coef: Clone + Default + Ring,
324    Exp: Clone + Ord + AdditiveMonoid,
325{
326}
327
328impl<Var, Coef, Exp> CommMonoid for Polynomial<Var, Coef, Exp>
329where
330    Var: Clone + Ord,
331    Coef: Clone + CommRig,
332    Exp: Clone + Ord + AdditiveMonoid,
333{
334}
335
336impl<Var, Coef, Exp> CommRig for Polynomial<Var, Coef, Exp>
337where
338    Var: Clone + Ord,
339    Coef: Clone + CommRig,
340    Exp: Clone + Ord + AdditiveMonoid,
341{
342}
343
344impl<Var, Coef, Exp> CommRing for Polynomial<Var, Coef, Exp>
345where
346    Var: Clone + Ord,
347    Coef: Clone + Default + CommRing,
348    Exp: Clone + Ord + AdditiveMonoid,
349{
350}
351
352impl<Var, Coef, Exp> CommAlg for Polynomial<Var, Coef, Exp>
353where
354    Var: Clone + Ord,
355    Coef: Clone + Default + CommRing,
356    Exp: Clone + Ord + AdditiveMonoid,
357{
358    type R = Coef;
359
360    fn from_scalar(r: Self::R) -> Self {
361        [(r, Monomial::one())].into_iter().collect()
362    }
363}
364
365#[cfg(test)]
366mod tests {
367    use super::*;
368
369    #[test]
370    fn polynomials() {
371        let x = || Polynomial::<_, i32, u32>::generator('x');
372        let y = || Polynomial::<_, i32, u32>::generator('y');
373        assert_eq!(x().to_string(), "x");
374
375        let p = Polynomial::<char, i32, u32>::from_scalar(-5);
376        assert_eq!(p.eval_pairs::<i32>([]), -5);
377
378        let p = x() * y() * x() * 2 + y() * x() * y() * 3;
379        assert_eq!(p.to_string(), "3 x y^2 + 2 x^2 y");
380        assert_eq!(p.map_variables(|_| 'x').to_string(), "5 x^3");
381        assert_eq!(p.eval_pairs([('x', 1), ('y', 1)]), 5);
382        assert_eq!(p.eval_pairs([('x', 1), ('y', 2)]), 16);
383        assert_eq!(p.eval_pairs([('y', 1), ('x', 2)]), 14);
384
385        let p = (x() + y()) * (x() + y());
386        assert_eq!(p.to_string(), "2 x y + x^2 + y^2");
387    }
388}
catlog/zero/alg.rs

catlog/zero/
alg.rs
