📘

Rustのenumの集合論的な見方：直和集合としてのenum

2020/11/02に公開

Rust

RustのenumはC++やJavaとは異なり非常に柔軟性の高いデータ構造になっている。これは代数型データ構造というもので、関数型言語やTypeScriptなどには実装されているものなのだが、知らない人にとっては慣れないものなので、簡単に説明するのが本記事の趣旨である。

直和集合

Rustのenumは代数的データ型というもので、これは集合論では直和集合に相当する。
本記事では立ち入らないが、structは直積集合に対応する。

直和集合とは和集合に近い概念で、二つの集合をそのままくっつけたものである。記号は $\sqcup$ を使う。和集合との違いは共通部分の扱いで、共通部分がない場合は直和集合と和集合は一致する。
具体例を見たほうが早いと思うので、例を見てみよう。

\begin{aligned} A &= \{a, b, c\} \\ B &= \{1, 2\} \\ A \sqcup B &= \{a, b, c, 1, 2\} \end{aligned}

上の例では $A$ と $B$ の共通部分がない（ $A\cap B=\emptyset$ ）なので和集合 $A\cup B$ と一致する。
次に共通部分がある場合を考える。この場合、ラベルづけすることで出自を残して和集合を取るイメージになる。

\begin{aligned} A &= \{a, b, c\} \\ B &= \{a, d\} \\ A \sqcup B &= \{a_A, b_A, c_A, a_B, d_B\} \end{aligned}

$a_A$ と $a_B$ は添字があることで区別され別のものとして扱われる。これが和集合との違いである。

enumと直和集合

直和集合がenumと同じであることを見てみよう。上の例をenumで表現すると以下のようになる。
ただし、 $A$ , $B$ をAlpha,Betaに、 $a,b,c,d$ をA,B,C,Dに置き換えた。

enum Alpha { A, B, C }
enum Beta { A, D }
enum Disjoint {
  Alpha(Alpha),
  Beta(Beta),
}

この例で、Alpha,Betaは普通の列挙型(C++などのenum)として定義している。型と集合、値と集合の要素が対応している。
DisjointがAlphaとBetaの直和集合になり、Alpha(A),Alpha(B),Alpha(C),Beta(A),Beta(D)の要素を値として取りうる。
※実際には名前空間が必要で、Disjoint::Alpha(Alpha::A)などと書く。列挙子Alphaと型名Alphaの区別に注意。

列挙子AlphaとBetaを使って、Alpha(A)とBeta(A)を別のものとして扱っているのが、前節の2つ目の例の添字による区別に対応している。この区別をどうやってやるのか、という疑問に対する解答がパターンマッチだ、と考えれば、enumとパターンマッチの相性のよさがわかる。

Option<T>、Result<T,E>を「入れ物」ではなく、「orの表現」と考える

enumを直和集合として見れるようになると標準で用意されているものも違って見れるようになる。
例えば、エラーや例外処理でよく使うOption<T>やResult<T,E>をこれまで入れ物と考えていなかっただろうか。実際にRustの公式ドキュメントではこれらを入れ物であるかのように説明し、本来返したい値をSomeやOkの「内部に保持」して、使うときにパターンマッチで「取り出す」という表現が使われている。
この説明を読んだときに、なんでそんな面倒なことをしないといけないのか、と思わなかっただろうか。筆者はそう思ってしまった。

しかし、直和集合として考えると至って自然な設計になっている。
例えばResult<i32,String>を返す関数であれば、i32型（=整数の集合）とString型（=文字列の集合）の直和集合の要素を返すので、返り値はi32の値（=整数）「または」Stringの値（=文字列）であると主張しているのである。
視覚化してみると以下のような違いである。

# 入れ物としての理解
Result --- Ok --- 1
              --- 2
              --- 3
       --- Err -- "Error 1"
	       -- "Error 2"

# 直和集合としての理解（orの表現）
Result --- 1 (Ok)
       --- 2 (Ok)
       --- 3 (Ok)
       --- "Error 1" (Err)
       --- "Error 2" (Err)

こう考えるとパターンマッチは「中の値を取り出す」ではなく、「出自に応じた条件分岐」になり、コードをスッキリ読めるようになるのではないだろうか。

また、Result<T,E>は和集合ではなく、直和集合が都合がいい例にもなっている。エラーを文字列ではなく、エラーコードとして整数型で表したい場合や、正常値も文字列、エラーも文字列といった具合に、TとEが一致する場合があり、このときは出自がわかる直和集合であることに意味が出てくる。

逆に言うと、それ以外のとき、すなわち要素がかぶらない場合は和集合と考えても問題ないということでもある。

JSON Valueの例

もう一つの例としてserde_json（JSONのシリアライザ/デシリアライザ）のValueの実装を見てみよう。

pub enum Value {
    Null,
    Bool(bool),
    Number(Number),
    String(String),
    Array(Vec<Value>),
    Object(Map<String, Value>),
}

JSONの値(Json Value)はnull、真偽値、数値、文字列、配列、オブジェクト（連想配列）のどれかとして定義されているが、それがそのまま列挙型で表現されている。配列やオブジェクトの値もJson Valueであって、nullや真偽値などの「どれか」なのだが、そのままValueを使われている。ここで、Valueの列挙子それぞれに対して入れ物のようなイメージを持ってしまうとわかりにくくなるかと思う。

C#やJavaなどのオブジェクト指向に囚われていると、複雑なデータ構造はなんでもstructで定義したくなってしまうが、enumだけで実装できていて、十分複雑な構造を定義できることがわかる。
※実際にはNumberがstructだが、さらにその中にenum N {PosInt(u64), NegInt(i64), Float(f64)}という列挙型が定義されている。

最後に

Rustのenumは直和集合（データ構造の名前としては代数的データ構造）である、ということを説明した。より実践的には「orの表現」と考えることができ、関数の引数や返り値を柔軟に設計できる。
近い概念にジェネリクス（静的・動的ディスパッチ）があるが、enumを使うとそれ以上のことができる。特に、トレイトでは関数の存在しか保証できないため、structのフィールドにアクセスしたいときは引数用にenumを定義しておいて、パターンマッチで条件分岐する、ということが必要になる。
また、返り値の型が実行時までわからない時にもenumが使えて、その典型例がOptionとResultである、ということだ。

直和集合

enumと直和集合

Option<T>、Result<T,E>を「入れ物」ではなく、「orの表現」と考える

JSON Valueの例

最後に

Discussion