上の記事で D として書かれているものを、利用者側が構造体を書かなくてもよいような方法で実装してみました。

だいたい次のような見た目となります。詳細は src/alg.rs

※今後もころころ宗旨替えすると思われます

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

trait Monoid<T: Copy> {
    fn unit(&self) -> T;
    fn op(&self, x: T, y: T) -> T;
    fn op_to(&self, y: T, x: &mut T) { *x = self.op(*x, y); }
}

struct MonoidImpl<T: Copy, Unit: Fn() -> T, Op: Fn(T, T) -> T>(pub Unit, pub Op);

impl<T: Copy, Unit: Fn() -> T, Op: Fn(T, T) -> T> Monoid<T> for MonoidImpl<T, Unit, Op> {
    fn unit(&self) -> T { (self.0)() }
    fn op(&self, x: T, y: T) -> T { (self.1)(x, y) }
}

struct SegmentTree<T, Alg> {
    len: usize,
    data: Vec<T>,
    alg: Alg,
}

impl<T: Clone, Alg: Monoid<T>> SegmentTree<T, Alg> {
    fn new(data: &[T], alg: Alg) -> Self { ... }
}

fn main() {
    let data = ...
    let mut rsq = SegmentTree::new(&data, MonoidImpl(|| 0, |x, y| x + y));
}

同様のものを trait Group などと定義しておきます。

整数型に対して struct Addition<T>; 等をあらかじめ作っておいてもよいと思います。

なお、MonoidImpl が単位元を含めて Fn で持っているのは、キャプチャがなければメモリ消費がないのできれいな気がしたからです。

利点

特に Rust っぽいもの

  • ライブラリの利用者側のコードが少ない
  • ある則を満たすときだけ実装ということができる。Binary Indexed Tree: Monoid なら prefix_sum を、さらに Group なら sum を実装するなど
  • 平衡二分木の各ノードに持たせるなどしてもメモリを消費しない

欠点

  • 種種の代数的構造の XxxImpl を用意すると嵩む
  • データ構造の merge で困る（クロージャを呼び出すために &self に手を出してしまったので、型が同じでも同じ代数的構造とは限らない）
  • そもそも抽象化やその方法を固定することは柔軟性を失いそう