基本的なデータ設計

さて，連結リストとは何でしょうか．基本的にはヒープ (カーネルのひとたち，静かに！) 上にある，順番にお互いを指すデータの断片の束のことです．連結リストは手続き型のプログラマにとっては長い棒でつんつんするのも避けたい代物ですが，関数型のプログラマはあらゆることに使います．それでは関数型プログラマに連結リストの定義を訊いてみましょう．きっとこんな返事が返ってくると思います:

List a = Empty | Elem a (List a)

これは，おおよそ「リストは空か，リストに続く要素のどちらかである」と読めます．これは再帰的な定義をタグ付き共用型 (sum type, tagged union type) を使って表したものです．ただし，タグ付き共用型というのは「異なる型の値を持つことができる型」というのをおしゃれに言ったものです．Rust ではこれを enum (列挙型) と呼んでいます．あなたが C 系の言語をすでにご存じなら，話が早いかもしれません．Rust の enum は，あなたが知っている（そして愛している）enum と同じものです．では，先ほどの関数型定義を Rust で書き直してみましょう．

今のところ，シンプルにするためジェネリクスは使わないでおきます．符号付き 32 ビット整数 i32 のみを格納することにします．

// in first.rs

// このモジュールを外部のひとが使えるように pub を付けています
pub enum List {
    Empty,
    Elem(i32, List),
}

ふー，忙しい忙しい．さっさとコンパイルしちゃいましょう．

> cargo build

error[E0072]: recursive type `first::List` has infinite size
 --> src/first.rs:4:1
  |
4 | pub enum List {
  | ^^^^^^^^^^^^^ recursive type has infinite size
5 |     Empty,
6 |     Elem(i32, List),
  |               ---- recursive without indirection
  |
  = help: insert indirection (e.g., a `Box`, `Rc`, or `&`) at some point to make `first::List` representable

なんだよ，関数型プログラマに騙された！（個人の意見です）

(裏切り行為を乗り越えた後) 実際にエラーメッセージを確認すると，実は rustc がこの問題を解決する方法を正確に教えてくれていることがわかります．

first::List を表すために，どこかで Box, Rc, & などの間接参照を用いてください

さてさて，Box ってなんでしょうね？ Rust box でググってみよう...．

std::boxed::Box - Rust

どれどれ...．

pub struct Box<T>(_);

ヒープ割り当てのためのポインタ型．詳しくは，モジュールごとのドキュメントを参照してください．

リンクをクリック．

Box<T> (通称 box) は，Rust で最も単純なヒープ割り当ての形式です．ボックスは，この割り当ての所有権を持ち，ボックスがスコープを抜けるとその内容が破棄されます．

例

ボックスを作る:

let x = Box::new(5);

再帰的なデータ構造を作る:


#![allow(unused)]
fn main() {
#[derive(Debug)]
enum List<T> {
    Cons(T, Box<List<T>>),
    Nil,
}
}

fn main() {
    let list: List<i32> = List::Cons(1, Box::new(List::Cons(2, Box::new(List::Nil))));
    println!("{:?}", list);
}

上のコードは Cons(1, Box(Cons(2, Box(Nil)))) と出力します．

次のような形の再帰的な定義はボックス化する必要があります．

Cons(T, List<T>),

そのままでは上手くいきません．なぜなら，リストのサイズがリスト自身に含まれている要素の数に依存するので， Cons に割り当てるべきメモリの量がわからないからです．ボックスはサイズが決まっているので，Cons に必要な大きさを事前に知ることができます．

ワーオ．こんなに適切で役に立つドキュメントは見たことがありませんね．私たちが書いたものがなぜ上手くいかなかったのか，そしてどう修正すれば良いのかがずばり書かれています．

やっぱりドキュメントは最高だな！

よし，やってみよう．

pub enum List {
    Empty,
    Elem(i32, Box<List>),
}

> cargo build

   Finished dev [unoptimized + debuginfo] target(s) in 0.22s

やった，ビルドが通ったぞ！

しかし，これはいくつかの理由から，実に愚かな定義です．

2つの要素を持つリストを考えてみましょう:

[] = スタック
() = ヒープ

[Elem A, ptr] -> (Elem B, ptr) -> (Empty, *junk*)

重要な問題が2つあります．

「ぼくはノードじゃない」というだけのノードを割り当てている．
ノードの一つに全くヒープが確保されていない．

表面的には，この2つは互いに打ち消しあうように見えます．余分なノードをヒープに割り当てる一方で，ノードの１つはヒープではなくスタックに割り当てています．しかし次のような設計のリストを考えてみてください．

[ptr] -> (Elem A, ptr) -> (Elem B, *null*)

この設計では，ノードは常にヒープに割り当てています．最初の設計との重要な違いは，ジャンクがないことです．このジャンクとは何でしょうか？それを理解するために，enum がどのようにメモリ上に配置されるかを見る必要があります．

一般的に，次のような enum があったとします:

enum Foo {
    D1(T1),
    D2(T2),
    ...
    Dn(Tn),
}

Foo は，それがどの列挙型のヴァリアント (D1, D2, .. Dn) を表しているかを示す整数を格納する必要があります．これを列挙型のタグといいます．また，T1, T2, .. Tn のうち最大のものを格納できるだけのスペースも必要です． (さらに，アラインメントの要件を満たすための余分なスペースも必要)．

ここで重要なのは，Empty が1ビットの情報であっても，いつでも Elem になれるように準備しなければならないので，ポインタと要素のために必要なスペースを必ず消費する，ということです．したがって，最初の設計ではヒープにジャンクでいっぱいの余分な要素が割り当てられ，2つめの設計よりも少し多くのスペースを消費してしまうのです．

ノードの一つをヒープに割り当てていないことも，悪いことです．なんでも常にヒープに割り当てる方がましです．これはノードの設計が不均一になるからです．ノードのプッシュやポップにはあまり影響しませんが，リストの分割やマージには影響します．

リストの分割を行ったときにどうなるか，両方の設計を比較してみましょう:

設計 1:

[Elem A, ptr] -> (Elem B, ptr) -> (Elem C, ptr) -> (Empty *junk*)

C で分割すると:

[Elem A, ptr] -> (Elem B, ptr) -> (Empty *junk*)
[Elem C, ptr] -> (Empty *junk*)

設計 2:

[ptr] -> (Elem A, ptr) -> (Elem B, ptr) -> (Elem C, *null*)

C で分割すると:

[ptr] -> (Elem A, ptr) -> (Elem B, *null*)
[ptr] -> (Elem C, *null*)

設計2の分割では，Bのポインタをスタックにコピーし，古いポインタを null にするだけです．設計1では同じことをするために，さらにCをヒープからスタックにコピーする必要があります．逆になるだけで，マージの場合も同様です．

ノード自体に要素を構築し，それを動かすことなくリスト間で自由に並び替えることができる点が，連結リストの数少ない長所でした．ポインターをいじるだけで，ものが「移動」するのです．設計1ではこの性質がゴミと化しています．

なるほど設計1がよくないことはわかりました．ではどのように書き換えればいいのでしょうか？そうですね，次のような方法はどうでしょう:

pub enum List {
    Empty,
    ElemThenEmpty(i32),
    ElemThenNotEmpty(i32, Box<List>),
}

これが更に悪いアイデアに見えることを祈ります．なぜなら，このリストには ElemThenNotEmpty(0, Box(Empty)) という完全に無効な状態が存在するからです．また，要素の割り当てが依然として一様でないことも問題です．

しかし，この設計には1つ興味深い特徴があります．Empty ケースの割り当てを完全に回避し，ヒープ割り当ての総数を1つ減らすことができるのです．残念なことに，これによって以前の設計で利用できていた ヌルポインタ最適化 が利用できなくなるので，さらにスペースを浪費する結果になってしまうのですが．

以前，すべての列挙型は，そのビットがどの列挙型のヴァリアントを表しているのかを指定するタグを格納しなければならないとご説明しました．しかし，その例外となる特別な種類の列挙型があります:

enum Foo {
    A,
    B(ContainsANonNullPtr),
}

この場合，ヌルポインタ最適化が行われ，タグにスペースを割くことがなくなります．もしヴァリアントが A ならば，enum 全体がすべて 0 に設定されます．そうでなければヴァリアントは B です．これが上手くいくのは, B はゼロでないポインタを含んでいるので，決してゼロにはならないからです．巧妙ですね．

他の列挙型や型でもこのような最適化ができるでしょうか？実はこういうケースはたくさんあります！ Rust が enum の設計を全く指定しないのはこのためです． Rust はもっと複雑な enum 設計の最適化も行ってくれますが，最も重要なのは間違いなくヌルポインタ最適化です．これは，&, &mut, Box, Rc, Arc, Vec, その他 Rust の重要な型が Option に入れられたとき，オーバーヘッドがないことを意味します！ (後で一部を紹介します)

では，どのようにすれば余分なジャンクを発生させず，割り当ても均一にし，ヌルポインタ最適化も行うということができるでしょうか？要素を持つことと，別のリストを割り当てることとをうまく切り離す必要があります．そのためには，もう少しC言語的に考える必要があります．構造体です！

列挙型では複数の値のいずれか ひとつ を格納できましたが，構造体では一度に 多くの 値を格納できます． List を「リスト」と「ノード」の２つの型に分割してみましょう．

前述したように，List は Empty (空) であるか，ある要素の後に別の List が続くかのどちらかです．この「要素があり，後に別のリストが続く」ケースを全く別の型で表現することで，Box を最適な位置にもっていくことができます．

struct Node {
    elem: i32,
    next: List,
}

pub enum List {
    Empty,
    More(Box<Node>),
}

チェックリストを確認していきましょう:

リストの末尾に余分なジャンクを割り当てない: OK ✅
enum のおいしいヌルポインタ最適化を利用できる: OK ✅
すべての要素が均一に割り当てられている: OK ✅

ヨシ！実はたったいま構築したのは，Rust の公式ドキュメントで提案されている設計がよくないことを示すために最初に使用した設計そのものです．

> cargo build

warning: private type `first::Node` in public interface (error E0446)
 --> src/first.rs:8:10
  |
8 |     More(Box<Node>),
  |          ^^^^^^^^^
  |
  = note: #[warn(private_in_public)] on by default
  = warning: this was previously accepted by the compiler but
    is being phased out; it will become a hard error in a future release!

また Rust が怒ってますね．List を (みんなが使えるように) パブリックにしたのですが，Node はパブリックにしませんでした． List の内部は完全にパブリックなので，その内部でプライベートな型について話すのは許されない，ということのようです． Node 全体をパブリックにすることもできますが，Rust では一般に実装の詳細をプライベートにしておくことが推奨されます．そこで，List を構造体にして，実装の詳細は隠しておけるようにしましょう．

pub struct List {
    head: Link,
}

enum Link {
    Empty,
    More(Box<Node>),
}

struct Node {
    elem: i32,
    next: Link,
}

構造体 List はフィールドを１つしか持たないので，そのサイズはフィールドのサイズと同じです．ゼロコスト抽象化です！やったね．

> cargo build

warning: field is never used: `head`
 --> src/first.rs:2:5
  |
2 |     head: Link,
  |     ^^^^^^^^^^
  |
  = note: #[warn(dead_code)] on by default

warning: variant is never constructed: `Empty`
 --> src/first.rs:6:5
  |
6 |     Empty,
  |     ^^^^^

warning: variant is never constructed: `More`
 --> src/first.rs:7:5
  |
7 |     More(Box<Node>),
  |     ^^^^^^^^^^^^^^^

warning: field is never used: `elem`
  --> src/first.rs:11:5
   |
11 |     elem: i32,
   |     ^^^^^^^^^

warning: field is never used: `next`
  --> src/first.rs:12:5
   |
12 |     next: Link,
   |     ^^^^^^^^^^

よし，コンパイルも通りました．Rust がだいぶ怒ってますが，これは Rust の知る限り私たちが書いたものが全く役に立たないからです．私たちは head を使用していませんし，私たちのライブラリを使う人もプライベートなので使うことができません．ということは，Link と Node も役に立たないということになります．では，それを解決しましょう！次は，いま作った私たちの List のためのコードを実装していきます．

Learning Rust With Entirely Too Many Linked Lists 日本語版

基本的なデータ設計