Rustと継承に関するメモ

はじめに

継承といっても#[derive(..)]のことではなくC++的な継承が欲しい場面でRustならどうするかという話。結論めいたものはない。アドバイスいただけると嬉しい。

発端

AtCoderの勉強にとRustでダイクストラ法の実装をおこなっていた。
いろいろ省略しているが以下の様なトレイトを作った。

mod dijkstra {

    #[derive(Copy, Clone, Eq, PartialEq)]
    pub struct State<T>
    {
        pub cost: usize,
        pub pos: T
    }

    pub trait Context<T>
    {
        fn cost(&self, pos: T) -> usize;
        fn update_cost(&mut self, s: &State<T>);
        fn neighbours(&self, s: &State<T>) -> Vec<State<T>>;

        fn run(&mut self, start: State<T>, end: T) -> Option<usize>
          where T: Copy+Ord {
            // 省略
        }
    }
}

あとは各問題に合わせてContextトレイトを実装すればよい（はず）。
ところで(全てではないが)多くの場合costはHashMapで管理すれば良さそうだ。
しかしトレイトにHashMapをメンバとして持たすことはできない、さてどうしようという話。

C++での実装

このときC++であればContextを継承してメンバと実装を持たせてしまうのが手っ取り早い。

// 疑似コード
class ContextWithHashMap : public Context {
    HashMap cost_table;

    size_t cost(T pos) {
        return cost_table[pos];
    }

    void update_cost(State<T>& s) {
        cost_table[s.pos] = s.cost;
    }
};

ユーザーはContextWithHashMapを継承してneighbours()の実装だけおこなえばよい。

Rustでの実装その１（差分をトレイトにする）

NeighbourトレイトとDefaultContextを新たに作る。
ユーザーはNeighbourトレイトを実装して、それを引数にDefaultContextを作ることになる。

    pub trait Neighbours<T>
    {
        fn neighbours(&self, s: &State<T>) -> Vec<State<T>>;
    }

    pub struct DefaultContext<'a, T, U>
    where U: 'a
    {
        pub cost_table: HashMap<T, usize>,
        pub data: &'a U
    }

    impl<'a, T, U> DefaultContext<'a, T, U>
    where T: Eq+Hash, U: Neighbours<T>
    {
        pub fn new(data: &'a U) -> Self {
            DefaultContext{ cost_table: HashMap::new(), data: data }
        }
    }

    impl<'a, T, U> Context<T> for DefaultContext<'a, T, U>
    where T: Copy+Clone+Eq+Hash, U: Neighbours<T>
    {
        fn cost(&self, pos: T) -> usize {
            self.cost_table.get(&pos).map_or(::std::usize::MAX, |c| *c)
        }

        fn update_cost(&mut self, s: &State<T>) {
            self.cost_table.insert(s.pos, s.cost);
        }

        fn neighbours(&self, s: &State<T>) -> Vec<State<T>> {
            self.data.neighbours(s)
        }
    }

むりやりC++っぽい実装を実現しようとするとこうなるだろうか。
DefaultContext::new()にNeighbourを渡すというのは回りくどいし、モジュール側のコードがC++より多いのもどうもいただけない。

Rustでの実装その２（ラムダ渡し）

DefaultContext作るところはその１と同じだが、neighbour()をラムダとして渡すようにしている。

    pub struct DefaultContext<'a, T: 'a>
    {
        pub table: HashMap<T, usize>,
        pub f: &'a Fn(&State<T>) -> Vec<State<T>>
    }


    impl<'a, T> Context<T> for DefaultContext<'a, T>
    where T: Copy+Clone+Eq+Hash
    {
        fn cost(&self, pos: T) -> usize {
            self.table.get(&pos).map_or(::std::usize::MAX, |c| *c)
        }

        fn update_cost(&mut self, s: &State<T>) {
            self.table.insert(s.pos, s.cost);
        }

        fn neighbours(&self, s: &State<T>) -> Vec<State<T>> {
            (self.f)(s)
        }
    }

    #[allow(dead_code)]
    pub fn create_default_context<'a, T, F>(f: &'a F) -> DefaultContext<'a, T>
    where T: Eq + Hash, F: Fn(&State<T>) -> Vec<State<T>> {
        DefaultContext{ table: HashMap::new(), f: f}
    }

その１よりはスマートな感じがするが、ユーザーが実装するメソッドが増えるとこの手は使えなさそう。

Rustでの実装その３（マクロ使用）

マクロを使ってみる

    macro_rules! cost_table {
        ($cost_table:ident, $t:ty) => (
            fn cost(&self, pos: $t) -> usize {
                self.$cost_table.get(&pos).map_or(::std::usize::MAX, |c| *c)
            }

            fn update_cost(&mut self, s: &State<$t>) {
                self.$cost_table.insert(s.pos, s.cost);
            }
        )
    }

ユーザーはこういう感じで使う

struct ContextImpl {
    cost_table: HashMap<(usize, usize), usize>
}

impl Context<(usize, usize)> for ContextImpl {
    cost_table!(cost_table, (usize, usize));

    fn neighbours(&self, s: &State<(usize, usize)>) -> Vec<State<(usize, usize)>> {
        // 省略
    }
}

モジュール側の実装は簡単だが、ユーザー側でHashMapを持ったり、マクロにStateの型パラメータを指定する必要があるのがかなりツライ。

まとめ

思いつく実装を３つほど挙げて見たもののどれもピンとこない。何かもっと良い実装はないだろうか。