3. im クレートによる永続データ構造

「変更しても元が壊れず、新しいバージョンが安く作れる」コレクション · 作成 2026-05-17

1. それは何か（一言）

「変更しても元の値が壊れず、新しいバージョンが安く作れる」コレクションです。

専門用語で 永続データ構造（persistent data structure） または 不変データ構造（immutable data structure） と呼ばれます。 Rust では im クレート (docs.rs/im) が事実上の標準実装です。

2. なぜ必要か — 普通のコレクションの問題

普通の Rust の std::collections::HashMap を使うと、こうなります:

let mut repo: HashMap<DataTag, ValueObj> = HashMap::new();
repo.insert(tag, value);  // ← mut が必要、元の repo は破壊的に変更される

ここに 3 つの問題があります:

問題	FP ガイドラインとの衝突
mut を書かないといけない	§2-1「イミュータブル中心」違反
「変更前の状態」が消える → undo/redo/履歴ができない	関数型の利点を活かせない
.clone() するとコレクション全体がコピー → 大きいと遅い	毎フレーム履歴を保存する用途で破綻

2-1. ScanDataPy の Repository が抱えている問題

ScanDataPy/model/model.py の Repository は内部リストを append / remove で 破壊的に更新しています:

# Python 版 Repository（簡略）
class Repository:
    def __init__(self):
        self._data = []   # mutable list

    def add(self, value_obj):
        self._data.append(value_obj)   # 破壊的更新

    def remove(self, tag):
        self._data = [d for d in self._data if d.data_tag != tag]

このため:

• undo/redo は実装が困難（全状態をスナップショットで複製する必要がある）
• 並行アクセスができない（mutate 中に他から読まれると壊れる）
• 「直前の状態と比較したい」が単なる diff にならない

3. im クレートが解決すること

use im::HashMap;

let repo: HashMap<DataTag, ValueObj> = HashMap::new();
let repo2 = repo.update(tag, value);  // 新しい HashMap を返す
// repo と repo2 は両方使える！元は壊れていない

ポイント:

• let mut が不要
• update(self, k, v) -> Self は新しい HashMap を返す（元は変えない）
• 元の repo と新しい repo2 が両方同時に存在できる
• 内部で構造共有するので、コピーコストは O(log n) でほぼ無料

4. 図解: 構造共有のしくみ

4-1. 普通の HashMap の .clone()

普通の HashMap を .clone() すると、内部の全要素を新しい領域にコピーします。

4-2. im::HashMap の .update() — 構造共有

im の HashMap は内部的に木構造でできていて、 更新するときには 変更した枝だけを新しく作り直し、 変わっていない枝は元の木と共有します。

5. 基本 API（HashMap を例に）

5-1. Cargo.toml に追加

[dependencies]
im = "15"

5-2. 主要メソッド

use im::HashMap;

// 作成
let m0: HashMap<String, i32> = HashMap::new();

// 追加・上書き → 新しい HashMap を返す
let m1 = m0.update("a".to_string(), 1);
let m2 = m1.update("b".to_string(), 2);

// 削除 → 新しい HashMap を返す
let m3 = m2.without(&"a".to_string());

// 取得（普通の HashMap と同じ）
let v: Option<&i32> = m2.get("a");

// イテレーション（普通の HashMap と同じ）
for (k, v) in &m2 {
    println!("{}={}", k, v);
}

// 元の m0, m1, m2 全部生きている！
assert_eq!(m0.len(), 0);
assert_eq!(m1.len(), 1);
assert_eq!(m2.len(), 2);
assert_eq!(m3.len(), 1);

5-3. 命名の覚え方

im のメソッド	std::HashMap の対応	違い
update(k, v)	insert(k, v)	im は self を取り Self を返す（非破壊）
without(&k)	remove(&k)	同上
get(&k)	同じ	同じ
contains_key(&k)	同じ	同じ

6. Repository を im で書く

use im::HashMap;
use crate::types::{DataTag, Filename};
use crate::value::ValueObj;

#[derive(Clone)]
pub struct Repository {
    items: HashMap<DataTag, ValueObj>,
}

impl Repository {
    pub fn new() -> Self {
        Self { items: HashMap::new() }
    }

    // 不変！ self を消費せず、新しい Repository を返す
    pub fn insert(&self, tag: DataTag, v: ValueObj) -> Self {
        Self { items: self.items.update(tag, v) }
    }

    pub fn remove(&self, tag: &DataTag) -> Self {
        Self { items: self.items.without(tag) }
    }

    pub fn get(&self, tag: &DataTag) -> Option<&ValueObj> {
        self.items.get(tag)
    }

    pub fn find_by_filename(&self, name: &Filename) -> Vec<&ValueObj> {
        self.items.iter()
            .filter(|(tag, _)| &tag.filename == name)
            .map(|(_, v)| v)
            .collect()
    }
}

使う側:

let repo = Repository::new();
let repo = repo.insert(tag1, value1);   // shadowing で「次の世代」を表現
let repo = repo.insert(tag2, value2);

7. 履歴・undo の実装

永続データ構造を使うと、履歴は Vec<Repository> に貯めるだけで実装できます:

pub struct RepoHistory {
    states: Vec<Repository>,
    cursor: usize,
}

impl RepoHistory {
    pub fn new() -> Self {
        Self {
            states: vec![Repository::new()],
            cursor: 0,
        }
    }

    pub fn current(&self) -> &Repository {
        &self.states[self.cursor]
    }

    // 新しい状態を push（先頭まで戻ってない場合は分岐先を捨てる）
    pub fn commit(self, next: Repository) -> Self {
        let mut states = self.states;
        states.truncate(self.cursor + 1);  // 内部 mut は許容
        states.push(next);
        Self { cursor: states.len() - 1, states }
    }

    pub fn undo(&self) -> Self {
        Self {
            states: self.states.clone(),
            cursor: self.cursor.saturating_sub(1),
        }
    }

    pub fn redo(&self) -> Self {
        Self {
            states: self.states.clone(),
            cursor: (self.cursor + 1).min(self.states.len() - 1),
        }
    }
}

ここで各 Repository のメモリは構造共有されているので、 1000 回 commit しても、コレクション全体を 1000 回コピーしているわけではありません。 変更箇所だけが新しく作られ、共通部分は共有されます。

8. 他のコレクション一覧

im の型	Rust 標準の対応	用途	ScanDataNet での使い道
im::HashMap<K, V>	std::HashMap	非破壊な辞書	Repository 本体
im::Vector<T>	Vec<T>	非破壊な動的配列	Modifier チェーンの並び順
im::HashSet<T>	std::HashSet	非破壊な集合	選択中の ROI 集合
im::OrdMap<K, V>	std::BTreeMap	ソート順を保つ非破壊辞書	時刻順イベント
im::OrdSet<T>	std::BTreeSet	ソート順を保つ集合	順序が大事な ID 集合

9. 学習ステップ（初心者向け）

段階	やること	目安時間
1	cargo new im-play --bin で新プロジェクトを作り、im = "15" を依存追加	15 分
2	im::HashMap::new() → update → get を 30 行で書く	30 分
3	let repo = repo.update(...); という shadowing に慣れる	30 分
4	let v1 = ...; let v2 = v1.update(...); assert!(v1.len() != v2.len()); で 非破壊性を確認	30 分
5	履歴 Vec<Repository> を作り、undo / redo を実装	1〜2 時間
6	iter().filter().collect() で find_by_keys 相当を書く	1 時間
7	im::Vector で Modifier チェーンの並びを表現し、insert / remove を試す	1 時間

10. 落とし穴

10-1. 巨大データには使わない

im::Vector<i16> で 256×256×1000 frame を入れると、木構造のオーバーヘッドが 無視できなくなります。ndarray（巨大配列）は Arc<Array3<i16>> で共有し、 im はValueObject の容器としてだけ使うのが正解です。

データ	容器
巨大 ndarray (raw frames など)	Arc<Array3<i16>>
ValueObject の集合 (Repository)	im::HashMap<DataTag, ValueObj>
Modifier の並び (短いリスト)	im::Vector<Modifier>

10-2. update と insert の違い

im::HashMap には非破壊な update(self, k, v) -> Self と 破壊的な insert(&mut self, k, v) -> Option<V> の両方があります。 FP 強寄りで書くなら必ず update を使う。

10-3. Clone トレイトが必要

中身（ValueObj）が Clone を実装していないと im::HashMap には入れられません。 巨大データは Arc<...> で包んでおくと Clone が参照カウントの加算だけで済んで安いです。

// ValueObj 自体は Clone 可能、中身は Arc で共有
#[derive(Clone)]
pub enum ValueObj {
    Frames(FramesData),
    Image(ImageData),
    // ...
}

#[derive(Clone)]
pub struct FramesData {
    pub data: Arc<Array3<i16>>,   // Clone はカウンタ +1 だけ
    pub tag: DataTag,
}

10-4. get の戻り値は Option<&V>

? 演算子で取り出すには Option を Result に変換する必要があります:

let v = repo.get(&tag)
    .ok_or(RepoError::NotFound(tag.clone()))?;

10-5. プロトコルや FFI に渡すとき

im::HashMap は serde でシリアライズ可能ですが、 WebSocket 越しに送る場合は受け側が std::HashMap を期待することが多いので、 境界では .into_iter().collect::<HashMap<_, _>>() で変換します。

11. まとめ

• im クレートは「変更しても元が壊れない・構造共有で軽い」コレクション
• 内部は木構造で、変更パス上だけ新規ノードを作成、それ以外は元と共有
• 更新コストは O(log n) で実用上ほぼ無料
• let mut 不要、shadowing で世代を表現できる
• 履歴・undo・タイムトラベルデバッグが Vec<Repository> で実装できる
• 巨大 ndarray は im ではなく Arc で共有する（使い分け重要）
• 必ず update / without を使う（破壊的な insert もあるので注意）

関連項目

• Option<T> の詳解 — get() -> Option<&V> の戻り値型と ok_or での Result 変換