代数的データ型Deep Dive in Scala

Scala

type-level-programming

Kazuki Moriyama (森山和樹)

関数型やってるとよく聞く代数的データ型(ADT)について。
Scalaやってるとよく使うがHaskellほどこの話題について掘った記事はあんまりないのでdigっていきたい。

そもそも代数的データ型とは

具体例

こういうやつ。

sealed trait Animal
case class Dog(name: String, age: Int) extends Animal
case class Cat(color: String) extends Animal

なぜ代数的データ型というのか

データ型をある種代数=計算対象とその上の演算・法則に対応させることができるからである。
例えば代数的データ型として定義されたものは足し算や掛け算の様なものに対応させることができる。
詳しくは後述する。

代数型データ型の構成要素

直和型

下のようなもので表されるもの。

sealed trait A
case class B(v: Int) extends A
case object C extends A

ここでAという型としてありえる具体型は、BまたはCとみなせる。
なぜなら他のファイルではAは継承できないし、new A {}のように直接インスタンス化することもできない。
(同一ファイル内でnew A {}することはできるっぽいがそれはなしの方向で)
故にAとしてありえる値のパターン数は「Bとしてありえる値のパターン数+Cとしてありえる値のパターン数」に等しい。
そしてBのパターンは内部のIntのパターン数 $2^{32}$ に等しくCは唯一Cだけがありえる値である。
結果として型に対応するありえる値の数を二重線文字で書くならば、

\begin{aligned} \mathbb{A} &= \mathbb{B} + \mathbb{C} \\ &= 2^{32} + 1 \end{aligned}

となる。
Aのパターンとして具体例を挙げると、
C、B(-2147483648)、…、B(2147483647)
と確かに $2^{32} + 1$ 個ある。

この様に直和型と言われるものの値の数はそのサブ型の値の数の和によって求められる。
代数的演算としては足し算に対応する。
しかもそのサブ型同士に被りはなく、集合論の直和集合に対応している。

これは仮にAとしてありえる値がB、C、D、…と増えていっても同じである。

以下型に対応する値の数をその型の二重線文字で表現する。

直積型

和に加えて積がもう一つの構成要素になる。
具体的には以下のようなものである。

case class B(v: Int)
object C
case class A(b: B, c: C)

ここで $\mathbb{A}$ を考えてみよう。
Aは２つの要素bとcによってなる。
つまりbの任意の要素に対してcの任意の要素の組を作ることができ、その数は $\mathbb{B} \times \mathbb{C}$
に等しい。
よって、

\begin{aligned} \mathbb{A} &= \mathbb{B} \cdot \mathbb{C} \\ &= 2^{32} \cdot 1 \\ &= 2^{32} \end{aligned}

となる。
Aのパターンとして具体例を挙げると、
A(B(-2147483648), C)、…、A(B(2147483647), C)
と確かに $2^{32}$ 通りになっている。

直積型の値の数はそれをなす型の数の積によって求められる。
代数的演算としては掛け算に対応する。

これは仮にAをなす要素がB、C、D、…と増えていっても同じ様にそれらの積をすればいいだけである。

代数的データ型の構造

代数的データ型は結局一番最初に出した例のように直和として表現される。
そしてそのサブ型は直積であるためしばしば「直積の直和」や、「直積の総和」などと表現されることもある。

データ型と代数

なんとなくデータ型を使った足し算と掛け算がわかったので、頻出するデータ型が代数的には何に対応するかを見ていこうと思う。

Nothing=0

Nothingは値がないことを保証する型で、例外を射出するときなどに使用する。
値がないのだから0である。

Unit=1

ScalaのUnitは唯一つの値()を持つため1に対応する。
同じ様にobjectなどのシングルトンたちも1に対応する。

Boolean=2

Booleanはtrueもしくはfalseの２値。
よって2。

Option[T]=T+1

Option[T]はSome(T)もしくはNoneである。
Someは単項直積でそのまま中身の値の種類に依存するため $\mathbb{T}$ でありNoneはシングルトンであるから、

\begin{aligned} \mathbb{Option}[T] &= \mathbb{T} + 1 \end{aligned}

である。

Either[A, B]=A+B

EitherはLeftもしくはRightでありどちらも単項直積で、

\mathbb{Either}[A, B] = \mathbb{A} + \mathbb{B}

である。
これは最も単純な直和であり、代数的データ型の例としてよく見る。

また仮に $\mathbb{B} = 1$ 、例えばBがUnitであるようなときは、

\begin{aligned} \mathbb{Either}[A, \text{Unit}] &= \mathbb{A} + 1 \\ &= \mathbb{Option}[A] \end{aligned}

となりこれはEither[A, Unit]とOption[A]が同じ表現力を持つことを示している。
確かに扱いやすさを別にすればRight[Unit]であることをNoneに、Left[A]であることをSome[A]に対応させれば同じことが表現できる。

他にも、Either[A, Nothing]なるものを考えれば、

\begin{aligned} \mathbb{Either}[A, \text{Nothing}] &= \mathbb{A} + 0 \\ &= \mathbb{A} \end{aligned}

となり単なるAに等しい。
Rightは起こり得ないのだからそれもそうである。

Tuple2[A, B]=A*B

タプルは任意の型の組み合わせを表現することができ、これは最も単純な直積である。
つまり、

\mathbb{Tuple2}[A, B] = A \cdot B

タプルの要素が2、3、…と増えていけば掛け算の項が増えていくだけ。

また仮にB=Nothingのときは、

\begin{aligned} \mathbb{Tuple2}[A, \text{Nothing}] &= \mathbb{A} \cdot 0 \\ &= 0 \\ &= \mathbb{Nothing} \end{aligned}

Nothingが入った瞬間に存在する値がないのだからそれはそう。

他にもB=Unitとすると、

\begin{aligned} \mathbb{Tuple2}[A, \text{Unit}] &= \mathbb{A} \cdot 1 \\ &= \mathbb{A} \end{aligned}

これも片方を()に固定してAの値を動かしていくだけなので表現力としては同じなのは腑に落ちる。

代数について

ここまで結構適当に代数というワードを使用してきたが、今一度代数とはなにかという部分を見ていきたい。

代数の構成

まず代数をなす要素から見ていく。
「代数」とは簡単に言えば次の３つの要素からなるものである。

何らかの集合A
集合Aの上での演算の集まり
演算が満たすべき法則

これら３つを備えたものを代数とか代数系とか呼んだりする。
またここでいう集合Aをunderlyingとか台集合とか呼んだりする。
イメージとしては集合Aが土台となって、その上で何らかの演算が定まり、それらが法則を満たしながら構成されているという感じ。

代数の具体例

代数の構成の定義だけ見てもなんのこっちゃわからないので具体例を見ていく。
下に上げたもの以外にも色々存在する

Semigroup(半群)

Catsとか使うと見たことある名前だと思う。
Semigroupは、

何らかの集合Aがあって
その上でなんらかの二項演算子 $*: A \times A \to A$ が定まっていて
Aの任意の要素a,b,cに対して $a(bc) = (ab)c$ が成り立っている(結合則)

とき、(A, *)の組をSemigroupと呼ぶ。
これもまた代数の具体例にしては抽象的なのでもっと具体化してみる。
Semigroupといっても実際にSemigroupになるようなものはいくつかあって、例えば自然数の集合Nとその上での足し算+の組(N, +)はSemigroupになっている。
なぜなら任意の自然数a、b、cに対して、 $(a + b) + c = a + (b + c)$ となるからだ。
ちなみに同様に掛け算に対してもNはSemigroupをなすが、割り算や引き算に対しては結果が自然数に収まらない( $1-2=-1$ )のでそれらに対してはSemigroupをなさない。

Monoid

Semigroupとほとんど同じ。
違うのは次の定義で定まる単位元を持つかどうか。

単位元とは、台集合Aの任意の要素aに対して、 $ea = ae = a$ となるようなAの要素eのこと

簡単に言うとその要素と別の要素の計算がその値を変化させないようなものである。
自然数の上での足し算の場合は0、自然数の上での掛け算は1がそれに対応する。

代数的データ型がなす代数

代数的データ型はどんな代数的構造が現れてくるか見ていきたい。

直和

直和として単純なEither[A, B]を見ていく。
例えば、

\begin{aligned} \mathbb{Either}[\mathbb{Either}[A, B], C] &= (\mathbb{A} + \mathbb{B}) + \mathbb{C} \\ &= \mathbb{A} + (\mathbb{B} + \mathbb{C}) \\ &= \mathbb{Either}[A, \mathbb{Either}[B, C]] \end{aligned}

となるのでEitherは結合則を満足する。
更に、

\begin{aligned} \mathbb{Either}[\text{Nothing}, A] &= 0 + \mathbb{A} \\ &= \mathbb{A} \\ &= \mathbb{A} + 0 \\ &= \mathbb{Either}[A, \text{Nothing}] \end{aligned}

となるのでEitherは単位元Nothingを持つ。
加えて、

\begin{aligned} \mathbb{Either}[A, B] &= \mathbb{A} + \mathbb{B} \\ &= \mathbb{B} + \mathbb{A} \\ &= \mathbb{Either}[B, A] \end{aligned}

よりEitherは可換(演算の項を入れ替えても結果が同じ)でもある。

以上からEitherは可換Monoidの性質を持つことがわかる。

直積

Tuple2[A, B]を考える。
例えば

\begin{aligned} \mathbb{Tuple2}[A, \mathbb{Tuple2}[B, C]] &= \mathbb{A} \cdot (\mathbb{B} \cdot \mathbb{C}) \\ &= \mathbb{A} \cdot \mathbb{B} \cdot \mathbb{C} \\ &= (\mathbb{A} \cdot \mathbb{B}) \cdot \mathbb{C} \\ &= \mathbb{Tuple2}[\mathbb{Tuple2}[A, B], C] \end{aligned}

であるからTuple2[A, B]は結合則を満足している。
更に、

\begin{aligned} \mathbb{Tuple2}[A, \text{Unit}] &= \mathbb{A} \cdot 1 \\ &= \mathbb{A} \\ &= 1 \cdot \mathbb{A} \\ &= \mathbb{Tuple2}[\text{Unit}, A] \end{aligned}

となりTuple2[A, B]は単位元Unitを持つ。
また零元(任意の要素との演算がまた零元になるような要素のこと)について考えてみると、

\begin{aligned} \mathbb{Tuple2}[A, \text{Nothing}] &= \mathbb{A} \cdot 0 \\ &= 0 \\ &= 0 \cdot \mathbb{A} \\ &= \mathbb{Nothing} \end{aligned}

となるので、Nothingが零元として振る舞う。

直積と直和

直積と直和の間の関係についても見ていく。
例えば以下の様なことが成り立つ。

\begin{aligned} \mathbb{Tuple2}[A, \mathbb{Either}[B, C]] &= \mathbb{A} \cdot (\mathbb{B} + \mathbb{C}) \\ &= \mathbb{A} \cdot \mathbb{B} + \mathbb{A} \cdot \mathbb{C} \\ &= \mathbb{Either}[\mathbb{Tuple2}[A, B], \mathbb{Tuple2}[A, C]] \end{aligned}

順番を逆にしても計算すると同様に

\mathbb{Tuple2}[\mathbb{Either}[A, B], C] = \mathbb{Either}[\mathbb{Tuple2}[A, C], \mathbb{Tuple2}[B, C]]

であることがわかる。
この様な関係を分配法則という。

Semiring

以上から代数的データ型は以下の性質を持つことがわかった。

和(Either[A, B])について可換Monoidをなす
積(Tuple2[A, B])についてMonoidをなす
積に零元が存在する
積は和の上で分配的に振る舞う

以上の性質を満たす代数的構造をSemiring(半環)という。
つまり代数的データ型はそれ自身がSemiring構造をなす。
これが代数的データ型が代数的と言われる所以である。

データ型で表されるその他の計算構造

以前の節で代数的データ型と代数についての話は終わったが、他のデータがで表される計算構造についてもついでなので見ていく。

関数

表現

関数の型は指数に対応する。
つまり、

\mathbb{Function1}[A, B] = \mathbb{B}^{(\mathbb{A})}

である。
これは集合論をちょっとかじった人なら見たことがあると思う。
なぜこうなるか見ていこう。
A => BはA型の各々の値にB型のある値を紐付ける操作だとみなすことができる。
そしてその紐付け方法は $\mathbb{B}$ 通りある。
$\mathbb{B}$ 通りの紐付け方法がAの要素分= $\mathbb{A}$ だけ存在するから、そのバリエーションは $\mathbb{B} \cdot \mathbb{B} \cdot \ldots \cdot \mathbb{B} = \mathbb{B}^{\mathbb{A}}$ である。

Unitを含んだ計算

関数表現の指数を使ってちょっと遊んでみる。

まず、

\begin{aligned} \mathbb{Function1}[A, \text{Unit}] &= 1^{\mathbb{A}} \\ &= 1 \\ &= \mathbb{Unit} \end{aligned}

となる。
どんなAに対してもUnitを返すならば、それは表現力としてはただのUnitと変わりないということだ。

逆にして考えてみると、

\begin{aligned} \mathbb{Function1}[Unit, A] &= \mathbb{A}^1 \\ &= \mathbb{A} \end{aligned}

となる。
引数が常にUnitの唯一の値()固定ならばあとはAのどれかの要素を返すだけ、つまりただAの要素から一つを選んでくるのに等しい。

指数法則

関数表現での指数法則を確かめてみる。

まず $(B \cdot C)^A = B^A \cdot C^A$ に対応するものを見てみると、

\begin{aligned} \mathbb{Function1}[A, \text{Tuple2}[B, C]] &= \text{Tuple2}[B, C]^{\mathbb{A}} \\ &= (\mathbb{B} \cdot \mathbb{C})^{\mathbb{A}} \\ &= \mathbb{B}^{\mathbb{A}} \cdot \mathbb{C}^{\mathbb{A}} \\ &= \text{Tuple2}[\mathbb{Function1}[A, B], \mathbb{Function1}[A, C]] \end{aligned}

となる。
最初の形のほうが適用は簡単だが、たしかにタプルに入った別々の関数に各々A型の値を適用しても表現力としては同じである。

次に $C^{(A \cdot B)} = (C^A)^B$ に対応するものを見てみると、

\begin{aligned} \mathbb{Function1}[\mathbb{Tuple2}[A, B], C] &= \mathbb{C}^{\mathbb{Tuple2}[A, B]} \\ &= \mathbb{C}^{(\mathbb{A} \cdot \mathbb{B})} \\ &= (\mathbb{C}^{\mathbb{A}})^{\mathbb{B}} \\ &= \mathbb{Function1}[B, \mathbb{Function1}[A, C]] \end{aligned}

となる。
この事実は本当に面白くて、カリー化された関数とカリー化する前の関数が本質的には同じであるという事実が指数法則に対応することを示している。

最後に $(A^B) \cdot (A^C) = A^{(B + C)}$ に対応するものを見たい。

\begin{aligned} \mathbb{Tuple2}[\mathbb{Function1}[B, A], \mathbb{Function1}[C, A]] &= (A^B) \cdot (A^C) \\ &= A^{(B + C)} \\ &= \mathbb{Function1}[\mathbb{Either}[B, C], A] \end{aligned}

となる。
これはEitherのfoldというメソッドを表現している。
foldはどちらの結果だろうとAという型に結果をマッピングするが、そのためにB => AとC => Aの２つの関数を引数として渡す必要がある。
foldの実態はこの２つの関数であることをこの法則は述べている。

List

Listがどういう計算体系に対応するかを見ていきたい。
まずListの定義は以下のよう。

sealed trait List[A]
case class Cons[A](head: A, next: List[A]) extends List[A]
case object Nil extends List[Nothing]

このデータ型の定式化はどうなるだろう？

まずListはConsとNilの直和なので以下が成り立つ。

\mathbb{List}[A] = \mathbb{Nil} + \mathbb{Cons}[A]

そしてConsはheadとnextの直積なので,

\mathbb{Nil} + \mathbb{Cons}[A] = \mathbb{Nil} + \mathbb{A} \cdot \mathbb{List}[A]

が成り立つ。
更にこれらを繰り返し適用すると、

\begin{aligned} \mathbb{List}[A] &= \mathbb{Nil} + \mathbb{Cons}[A] \\ &= \mathbb{Nil} + \mathbb{A} \cdot \mathbb{List}[A] \\ &= \mathbb{Nil} + \mathbb{A} \cdot (\mathbb{Nil} + \mathbb{Cons}[A]) \\ &= \mathbb{Nil} + \mathbb{A} \cdot \mathbb{Nil} + \mathbb{A} \cdot \mathbb{Cons}[A] \\ &= \mathbb{Nil} + \mathbb{A} \cdot \mathbb{Nil} + \mathbb{A}^2 \cdot \mathbb{List}[A] \\ &= \mathbb{Nil} + \mathbb{A} \cdot \mathbb{Nil} + \mathbb{A}^2 \cdot \mathbb{Nil} + \mathbb{A}^3 \cdot \mathbb{Nil} + \ldots \quad (\mathbb{Nil} = 1) \\ &= 1 + \mathbb{A} + \mathbb{A}^2 + \mathbb{A}^3 + \ldots \quad (\mathbb{Nil} = 1) \end{aligned}

のように無限級数になる。
何じゃこりゃと思えるかもしれないが、実際のデータ型に対応させてみるとわかりやすい。
Listはそもそもどんなデータ構造だったかと言うと、任意の長さのAの要素を並べたものである。
例えば空っぽのList=List()はただ一通りしか存在しない。
長さが1のListはAのどの要素を一つ格納するかで $\mathbb{A}$ 通りある。
長さ2の場合は１つ目の格納する要素がどれかで $\mathbb{A}$ 通り、２つ目も同様に $\mathbb{A}$ 通りあるから全体として $\mathbb{A}^2$
…
長さnの場合は同様に $\mathbb{A}^n$ 通り。
という感じになる。
つまり $1 + \mathbb{A} + \mathbb{A}^2 + \mathbb{A}^3 + \ldots$ の各項はListの長さに応じたデータのバリエーションを表している。

さてListの定式化をもうちょっといじってみよう。
$\mathbb{Nil} = 1$ だから、

\begin{aligned} \mathbb{List}[A] = 1 + \mathbb{A} \cdot \mathbb{List}[A] \end{aligned}

両辺から $\mathbb{A} \cdot \mathbb{List}[A]$ を引いて、

\begin{aligned} \mathbb{List}[A] - (\mathbb{A} \cdot \mathbb{List}[A]) &= 1 \\ \mathbb{List}[A](1 - \mathbb{A}) &= 1 \\ \mathbb{List}[A] &= \frac{1}{(1 - \mathbb{A})} \end{aligned}

となんか面白い結果が出てくる。
今まで型に対する和（Eitherとか）と積（Tupleとか）は定式化したが引き算とわり算は定式化していない。
この問題に対して意味を付与する論文もあるみたいだがそのためには追加の言語セマンティクスが必要らしい（読んでいないのであんまり良くわからん。）

一旦引き算とわり算の問題は無視してもうちょっと深ぼってみよう。

先に得られた等式 $\mathbb{List}[A] = \frac{1}{1 - \mathbb{A}}$ の右辺を $\mathbb{A}$ に関して微分してみる。

\begin{aligned} \frac{d}{d\mathbb{A}} \frac{1}{1 - \mathbb{A}} &= \frac{d}{du} \frac{1}{u} \cdot \frac{d}{d\mathbb{A}} (1 - \mathbb{A}) \quad (u = \frac{1}{1 - \mathbb{A}}, \text{合成関数の微分})\\ &= (-\frac{1}{u^2}) \cdot (-1)\\ &= (\frac{1}{u})^2\\ &= (\frac{1}{1 - \mathbb{A}})^2\\ &= \mathbb{Tuple2}[List[A], List[A]] \end{aligned}

なんとListを微分するとListのペアになる。
もはやここまで来るとこれに何の意味があるのかわからなくなってくるが、この型（Listのペア）に対応するデータ型がありそれをzipperという。
このデータ型が表すのはListを走査する処理を抽象化し、いまListのどの位置にカーソルをおいているか、カーソルの左右にどのようなListがあるかをデータとして持ち、カーソルの位置に対して操作を行ったりカーソルの移動を行うことができる。
具体的な実装例はこのブログなどを参照してほしい。
zipperはlist以外にも木構造のような再帰的なデータ型には定義できるらしく、それらも元のデータ型との微分表現によるつながりを持つらしい。
特にHListに対して定義されたshapelessのzipperは興味深い。
他にもcirceなどはJson型に対してのzipper的な操作を用意してある。

ただなぜ微分表現がこのような関係性を生むかは正直理解できていない。

終わり

掘れば掘るほどわからないことは出てくるので、また時間を見つけて色々調べたい。

参考