Trait Monoid 

pub trait Monoid: SemiGroup + Unital {
    // Provided methods
    fn pow<E>(x: Self::T, exp: E) -> Self::T
       where E: ExpBits { ... }
    fn fold<I>(iter: I) -> Self::T
       where I: IntoIterator<Item = Self::T> { ... }
}

associative binary operation and an identity element

Provided Methods

fn pow<E>(x: Self::T, exp: E) -> Self::T

where E: ExpBits,

binary exponentiation: $x^n = x\circ\ddots\circ x$

Examples found in repository

crates/competitive/src/algorithm/sqrt_decomposition.rs (line 135)

    fn fold_bucket(bucket: &Self::B) -> <Self::M as Magma>::T {
        M::operate(&bucket.0, &M::pow(bucket.1.clone(), bucket.2))
    }

crates/competitive/src/algebra/magma.rs (line 225)

    fn signed_pow<E>(x: Self::T, exp: E) -> Self::T
    where
        E: SignedExpBits,
    {
        let (neg, exp) = E::neg_and_bits(exp);
        let res = Self::pow(x, exp);
        if neg { Self::inverse(&res) } else { res }
    }

crates/competitive/src/string/rolling_hash.rs (line 521)

    fn muln_add(&mut self, x: &R::T, y: &R::T, n: usize) -> R::T {
        if let Some(pow) = self.pow.get(n) {
            R::add(&R::mul(x, pow), y)
        } else {
            let pow = <R::Multiplicative as Monoid>::pow(self.base.clone(), n);
            R::add(&R::mul(x, &pow), y)
        }
    }
    fn muln_sub(&mut self, l: &R::T, r: &R::T, n: usize) -> R::T {
        if let Some(pow) = self.pow.get(n) {
            R::sub(r, &R::mul(l, pow))
        } else {
            let pow = <R::Multiplicative as Monoid>::pow(self.base.clone(), n);
            R::sub(r, &R::mul(l, &pow))
        }
    }

crates/competitive/src/math/floor_sum.rs (line 259)

fn floor_monoid_product<M>(
    mut x: M::T,
    mut y: M::T,
    mut n: u64,
    mut a: u64,
    mut b: u64,
    mut m: u64,
) -> M::T
where
    M: Monoid,
{
    let mut c = (a * n + b) / m;
    let mut pre = M::unit();
    let mut suf = M::unit();
    loop {
        let (p, q) = (a / m, b / m);
        a %= m;
        b %= m;
        x = M::operate(&x, &M::pow(y.clone(), p));
        pre = M::operate(&pre, &M::pow(y.clone(), q));
        c -= p * n + q;
        if c == 0 {
            break;
        }
        let d = (m * c - b - 1) / a + 1;
        suf = M::operate(&y, &M::operate(&M::pow(x.clone(), n - d), &suf));
        b = m - b - 1 + a;
        n = c - 1;
        c = d;
        swap(&mut m, &mut a);
        swap(&mut x, &mut y);
    }
    x = M::pow(x.clone(), n);
    M::operate(&M::operate(&pre, &x), &suf)
}

crates/competitive/src/algorithm/baby_step_giant_step.rs (line 19)

pub fn baby_step_giant_step<M>(x: M::T, y: M::T, n: usize) -> Option<usize>
where
    M: Monoid<T: Eq + Hash>,
{
    if M::is_unit(&y) {
        return Some(0);
    }
    let block_size = 1usize.max((n as f64).sqrt() as _);
    let mut baby = HashSet::new();
    let mut t = y.clone();
    for _ in 0..block_size {
        t = M::operate(&x, &t);
        baby.insert(t.clone());
    }
    let g = M::pow(x.clone(), block_size);
    let mut t = M::unit();
    let mut fail = 0usize;
    for k in (0..n).step_by(block_size) {
        let nt = M::operate(&g, &t);
        if baby.contains(&nt) {
            for m in k..n.min(k + block_size) {
                if t == y {
                    return Some(m);
                }
                t = M::operate(&x, &t);
            }
            fail += 1;
            if fail >= 2 {
                break;
            }
        }
        t = nt;
    }
    None
}

fn fold<I>(iter: I) -> Self::T

where I: IntoIterator<Item = Self::T>,

Dyn Compatibility

This trait is not dyn compatible.

In older versions of Rust, dyn compatibility was called "object safety", so this trait is not object safe.

Implementors

impl<M> Monoid for M

where M: SemiGroup + Unital,