Help us understand the problem. What is going on with this article?

Rustと継承に関するメモ

More than 1 year has passed since last update.

はじめに

継承といっても#[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での実装その1(差分をトレイトにする)

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での実装その2(ラムダ渡し)

DefaultContext作るところはその1と同じだが、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}
    }

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

Rustでの実装その3(マクロ使用)

マクロを使ってみる

    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の型パラメータを指定する必要があるのがかなりツライ。

まとめ

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

itage
ITAGEは「IT」のAGENCYになることを夢、目標として進化、変化していきます。「It’s It Agency」
http://www.itage.co.jp
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
No comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
ユーザーは見つかりませんでした