Rust で Linked List を実装する(2. 永続スタック編)

はじめに

前回の記事で単方向連結リストを実装しました。
zaki-joho.hatenablog.com

単方向連結リストがあるということは? そうですね、永続スタックを実装することができます!
今回の記事は Introduction - Learning Rust With Entirely Too Many Linked Lists の第4章に相当します。

ソースコードは gist (persistent stack · GitHub) に置いてあるので適宜参照してください。

相変わらず Rust 全然分かってないので間違いがあればコメント欄なりで指摘してください。

永続スタック(persistent stack)

永続スタックについておさらいしておきましょう。
まず [A, B, C, D] という要素を持つスタック1があるとします。スタック1 の先頭を取り除いたもの(=[B, C, D])をスタック2とします。そしてスタック2に要素 [X] を追加したもの(=[X, B, C, D])をスタック3とします。

図にするとこんな感じです。

f:id:zaki_joho:20200620220200p:plain
永続スタック

この3つのスタックを管理したいとき、どうすれば良いでしょうか。全ての要素をコピーして別々のスタックとして扱う方法もありますが、要素数が多くなると無駄が多くなりそうです。図を見ると各操作の後に要素の大半は変化していないことが分かります。
新しくスタックを作るとき、先頭要素だけ新しく作成して残りの要素は元のスタックを参照するといい感じに表せそうですね!

永続スタックでは次の操作が O(1) で可能です。

  • head(): 先頭要素にアクセス
  • append(T x): 要素 x を追加して得られるスタック作成
  • tail(): 先頭要素を削除して得られるスタックを作成

更に知りたい方は先行研究 あなたの庭に永続データ構造を飾りませんか? - noshi91のメモ が詳しいです。

実装

永続スタックを完全に理解したところで実装していきます。

構造体

まずは永続スタックを表す構造体を定めます。

use std::sync::Arc;

struct List<T> {
    head: Link<T>,
}

type Link<T> = Option<Arc<Node<T>>>;

struct Node<T> {
    elem: T,
    next: Link<T>,
}

いきなり Arc が出てきてしまいました。
永続スタックを実装するにあたって、上の図を見直してみると要素 A は複数のスタックから参照されていることが分かります。
各スタックに好き勝手されては困るので、参照カウンタである Arc で管理します。今回は別にマルチスレッドで動かすわけでもないので Rc でもいいのですが、折角なので Arc を使っておきましょう。

正直理解できてるか怪しいので、Rustの `Arc` を読む(1): Arc/Rcの基本 - Qiita を読んで勉強中です。

それ以外の部分は前回と同じように書けます。

操作

構造体が書けたところで各操作を実装していきます。

impl<T> List<T> {
    fn new() -> Self {
        List { head: None }
    }

    fn append(&self, elem: T) -> List<T> {
        List {
            head: Some(Arc::new(Node {
                elem: elem,
                next: self.head.clone(),
            })),
        }
    }

    fn tail(&self) -> List<T> {
        List {
            head: self.head.as_ref().and_then(|node| node.next.clone()),
        }
    }

    fn head(&self) -> Option<&T> {
        self.head.as_ref().map(|node| &node.elem)
    }
}

new(), head() は前回と一緒です。
tail() はスタックが既に空のときにも処理できるように map() でなく and_then() を使います。
append() が少し問題で、Arc を使って先頭要素への参照を作成する必要があります。

イテレータ

ついでに今回もイテレータを実装します。
mutable にすると大変なことになる(というかコンパイルできるんですか?)ので今回は immutable なイテレータだけです。

struct Iter<'a, T> {
    next: Option<&'a Node<T>>,
}

これは前回と同じですね。

impl<T> List<T> {
    fn iter(&self) -> Iter<'_, T> {
        Iter {
            next: self.head.as_ref().map(|node| &**node),
        }
    }
}

impl<'a, T> Iterator for Iter<'a, T> {
    type Item = &'a T;

    fn next(&mut self) -> Option<Self::Item> {
        self.next.map(|node| {
            self.next = node.next.as_ref().map(|node| &**node);
            &node.elem
        })
    }
}

こっちも丸写しで完成してしまいました、楽ちん。

感想

ほぼ Arc で包むだけで永続スタックが書けてしまいました。これで庭が賑やかになりますね。
Drop trait を実装していないので実際に使うとき(あるか?)は注意してください。

次回は Doubly linked list を実装する予定です。目次に "A Bad but Safe Doubly-Linked Deque" とか書かれているんですがどうなってしまうんでしょうか。