monoid.md

モノイド

trait Monoid
where
    Self: PartialEq + std::fmt::Debug + Sized + Clone,
{
    const E: Self; // 単位元

    /// 乗算演算。self * rhs。 Self x Self -> Self
    fn op(self, t: Self) -> Self;

    /// 単位元に関する条件
    fn require_unit(t: Self) {
        assert_eq!(Self::E.op(t.clone()), t); // E * t == t
        assert_eq!(t.clone().op(Self::E), t); // t * E == t
    }

    /// 結合則
    fn require_associativity(t1: Self, t2: Self, t3: Self) {
        // (t1 * t2) * t3 == t1 * (t2 * t3)
        assert_eq!(t1.clone().op(t2.clone()).op(t3.clone()), t1.op(t2.op(t3)));
    }
}

#[derive(Debug, PartialEq, Clone)]
enum List<T> {
    Nil,
    Cons(T, Box<List<T>>),
}

/// Listは自由モノイド
impl<T: PartialEq + std::fmt::Debug + Clone> Monoid for List<T> {
    const E: Self = List::<T>::Nil;

    /// 2つのリストの結合
    fn op(mut self, t: Self) -> Self {
        let mut node = &mut self;
        while let List::<T>::Cons(_, next) = node {
            node = next;
        }

        *node = t;
        self
    }
}

fn main() {
    let list1 = List::Nil;
    let list1 = List::Cons(0, Box::new(list1));
    let list1 = List::Cons(1, Box::new(list1));
    let list1 = List::Cons(2, Box::new(list1));

    let list2 = List::Nil;
    let list2 = List::Cons(110, Box::new(list2));
    let list2 = List::Cons(220, Box::new(list2));
    let list2 = List::Cons(330, Box::new(list2));

    let list3 = List::Nil;
    let list3 = List::Cons(-67, Box::new(list3));
    let list3 = List::Cons(-40, Box::new(list3));

    // 単位元？
    Monoid::require_unit(list1.clone());
    Monoid::require_unit(list2.clone());
    Monoid::require_unit(list3.clone());

    // 結合則?
    Monoid::require_associativity(list1, list2, list3);
}