帰納的型

Essential
最終更新: タグ: Rust, ADT

前提知識

帰納的型（inductive type）とは、有限個のコンストラクタ（constructor）のリストによって定義される型だ。各コンストラクタはその型の値にどんなデータをまとめるかを指定し、すべての値はちょうど一つのコンストラクタによって生成される — match によって実行時に必ず識別できる。

このアイデアは数学に由来する。自然数は帰納的に定義される。0 は自然数（基底ケース）であり、n が自然数であれば n + 1 も自然数（帰納ステップ）だ。すべての自然数はこの二つの規則を有限回適用することで到達できる。

データ型も同じパターンに従う。

コンストラクタ

コンストラクタとは、その型の値を作る方法だ。直積型はコンストラクタを一つ持つ — すべてのフィールドを受け取る構造体リテラルだ。

struct Point { x: f64, y: f64 }
// コンストラクタ一つ: Point { x: …, y: … }

直和型はバリアントごとにコンストラクタを一つ持つ。

enum Color { Red, Green, Blue }
// コンストラクタ三つ; それぞれ引数なし

バリアントはデータを持てるので、より豊かなコンストラクタになる。

enum Expr {
    Num(f64),
    Add(Box<Expr>, Box<Expr>),
    Mul(Box<Expr>, Box<Expr>),
}

Num は f64 を一つ受け取る。Add と Mul はそれぞれ二つの部分式を受け取る。定義が自分自身を参照しているため、部分式は Box でラップして型に有限のサイズを与える（後述の帰納的型 — 再帰ケースには間接参照が必要を参照）。

構造的再帰

帰納的型のすべての値は特定のコンストラクタによって構築されているため、どのコンストラクタが使われたかをマッチして各部分に再帰することで解析できる。

fn eval(expr: &Expr) -> f64 {
    match expr {
        Expr::Num(n)    => *n,
        Expr::Add(l, r) => eval(l) + eval(r),
        Expr::Mul(l, r) => eval(l) * eval(r),
    }
}

このパターン — コンストラクタにマッチして部分値に再帰する — を構造的再帰（structural recursion）と呼ぶ。自動的に停止する。各再帰呼び出しは厳密に小さい値（部分式）に対して動作し、基底ケース（Num）には再帰する部分値がない。

再帰ケースには間接参照が必要

Rustはすべての型のサイズをコンパイル時に計算する。裸の再帰定義はサイズが無限になる。

// error: recursive type `Expr` has infinite size
enum Expr {
    Num(f64),
    Add(Expr, Expr), // 二つの Expr を含む Expr がさらに二つの Expr を含む…
}

修正方法は、固定サイズの間接参照で無限の後退を断ち切ることだ。標準的なツールは Box<T> で、部分値をヒープに格納してそのポインタを保持する。ポインタは指し示す対象に関係なく常にポインタサイズだ。

enum Expr {
    Num(f64),
    Add(Box<Expr>, Box<Expr>), // ok: Box<Expr> はポインタ一つ分のサイズ
    Mul(Box<Expr>, Box<Expr>),
}

コンパイラは Box が必要なときに教えてくれる — エラーメッセージに明示されている。

数学的帰納法との対応

これらの型が帰納的と呼ばれる理由は、値に関する性質を帰納法によって証明できるからだ — 定義の構造にそのまま従う形で。

  • 基底ケース（再帰フィールドを持たないコンストラクタ）について性質を証明する。
  • すべての部分値について性質が成り立つと仮定して、再帰コンストラクタについて性質が成り立つことを証明する。

これは eval と同じ形だ。Num のアームが基底ケースで、Add と Mul のアームが帰納ステップだ。構造的再帰関数はどれも、その型に関する暗黙の帰納的証明だ。