trait Semigroup {
fn compose(&self, other: &Self) -> Self;
}
trait Monoid: Semigroup {
fn identity() -> Self;
}
Any semigroup can trivially be made into a monoid by adding an identity element:
impl<T: Semigroup + Clone> Semigroup for Option<T> {
fn compose(&self, other: &Self) -> Self {
match self {
Some(ref a) => match other {
Some(ref b) => Some(a.compose(b)),
None => self.clone()
},
None => other.clone()
}
}
}
impl<T: Semigroup + Clone> Monoid for Option<T> {
fn identity() -> Self {
None
}
}
Now we have our interface for an eager arqtree.
pub struct ArqTree<T> {
val: Vec<T>
}
impl<T: Monoid + Clone> ArqTree<T> {
fn modify(&mut self, pos: usize, f: fn(&T) -> T) {
// implement modify
}
fn query(&self, l: usize, r: usize) -> T {
// implement query
}
}
However, this will not suffice when we need to do range updates!