代数 - 作用 - 代入作用

代入を表現する 右 作用を定義する.

集合 \(X\) について,

\[A_X = X \sqcup \{ \bot \}\]

は, 代入（または値の上書き）をする作用 \((\ast)\) を表現する.

• 作用
  • \(x \ast a = a~~~\) if \(a \ne \bot\)
  • \(x \ast \bot = x\)
• 合成
  • \(ab = b~~~\) if \(b \ne \bot\)
  • \(a \bot = a\)
  • \(x \ast (ab) = (x \ast a) \ast b~~\) where \(x \in X ,~ a,b \in A_X\)

Min/Max モノイド と組み合わせてモノイド作用付きモノイドとしたとき, これを 遅延セグメントツリー に載せると, 区間更新の出来る RMQ になる.

/// Algebra - Assign Monoidal Act
use crate::algebra::act::*;
use crate::algebra::monoid::*;
use crate::monoid; // IGNORE

#[derive(Debug, Clone, Copy)]
pub enum Assign<X> {
    Some(X),
    None,
}
monoid! {
    Assign<X> where [X];
    one = Assign::None;
    mul(self, other) = {
        match (self, &other) {
            (x, Assign::None) => x,
            _ => other,
        }
    }
}
impl<X: Copy> Act<X> for Assign<X> {
    fn act(&self, other: X) -> X {
        match *self {
            Assign::None => other,
            Assign::Some(x) => x,
        }
    }
}

#[cfg(test)]
mod test_act_assign {
    use crate::algebra::act_assign::*;
    #[test]
    fn it_works() {
        assert_eq!(Assign::Some(1).act(0), 1);
        assert_eq!(Assign::None.act(0), 0);
        assert_eq!((Assign::Some(1) * Assign::Some(2)).act(0), 2);
        assert_eq!((Assign::None * Assign::Some(2)).act(0), 2);
        assert_eq!((Assign::Some(1) * Assign::None).act(0), 1);
        assert_eq!((Assign::None * Assign::None).act(0), 0);
        assert_eq!((Assign::None * Assign::None * Assign::Some(9)).act(0), 9);
    }
}