リストを題材にして代数的データ構造に入門してみる

こちらの記事はカケハシ Advent Calendar 2022 の 7日目の記事になります。 https://adventar.org/calendars/7444

この記事のモチベーション

カケハシでAI在庫管理というプロダクトのバックエンド開発をやっている金子です。

代数的データ構造というデータ構造について聞いたことはありますでしょうか。
私はあります。が、それが何なのか、なぜ「代数的」と呼ばれるのか良く分かっていません。

そこで、この記事では代数的データ構造のことを良くわかっていない私が、代数的データ構造のことを知らない人に向けて、代数的データ構造について説明してみる、という無謀な試みにチャレンジしてみたいと思います。

この記事の対象読者

代数的データ構造という名前は聞いたことがあるけど、それが何か良くわからない方です。
そういった方に、代数的データ構造とは何か、どの様な特徴があるのかのイメージを掴んでいただけることをゴールにします。

あくまで大枠のイメージを掴んで頂くことが目的なので、厳密さについては目をつぶることにします。

代数的データ構造の例：リスト

大まかなイメージを掴んで頂くには、抽象的な話をするよりも、具体例を上げる方が良さそうなので、プログラマーの方にとってはとても身近な「リスト」を具体例にして、話を進めていきたいと思います。

TypeScriptやPythonではリスト/Arrayは基本型で、ユーザーがその型定義を見ることはできません。
一方で、Haskellでは、Listについてもその型定義を見ることができます。

試しにghci（Haskellのいわゆるreplです）を起動して、

:info []
として、リストの型定義を確認してみると

data [a] = [] | a : [a]
と出力されます。確かにリストの型定義を確認することができました。

実は、これが代数的データ構造の1つで、Haskellではリストも代数的データ構造を使って表現されています。
（実際の出力では、リストの表現が [a] と [] a で表記ゆれしているなど、少し分かりづらいので、微修正しています。実際にご自身で試してみる際にはご注意ください）

Haskellの記法から離れて、もう少し一般的な表現で代数的データ構造による、リストの定義を書いてみます。

List a = Nil | Cons a (List a)
ここで使われている

・「a」は型変数です
・Nilはsingleton（引数を取らない型コンストラクタ）を表しています。つまりここでは「空リスト」を表しています
・「|」は「または」の意味です。TypeScriptのUnionと同様です
・Consは第2引数として渡されるリストの先頭に、第1引数を追加する操作です
これが代数的データ構造による、リストの表現です。
ghciで表示されたリストの表現と、おおよそ対応しているように見えるのではないでしょうか。

でも、このデータ型のどこが「代数的」なのでしょうか。

代数的なデータとは

リストからは一度離れて（後でまた戻ってきます）、代数的なデータとは何かについて考えます。
代数的なデータの大まかなイメージは「代数的な表現・操作ができるデータ」です。
つまり

データが

・足し算 (sum)
・掛け算 (product)
といった形式で表現され、代数のようにその表現を変形することができるデータ、です。
だいぶ抽象的でわかりにくくなってきました。

足し算によって表現されるデータと、掛け算によって表現されるデータ、それぞれについて見ていきましょう。

「足し算」によって表現できるデータ型

「足し算」によって表現できるデータ型はsum typesと呼ばれ、以下の様なデータ型がこれにあてはまります

・Union
・Enum
・Maybe
・Either
たとえば、「X」がA or B or Cのどれかの型を取る型であれば、Xは

type X = A | B | C
のように表現できます。
これを代数的な表現に変換すると

X = A + B + C
というように、型の足し算として表現できます。

なぜこのように表現してよいのかを説明を始めると、「大まかなイメージを掴む」というこの記事の目的から逸れてしまうので、今回は説明を省略しますが、論理演算において「or」が「論理”和”」と呼ばれることとのアナロジーで直感的イメージは掴んで頂けるのではないでしょうか。

「掛け算」によって表現されるデータ構造

「掛け算」によって表現されるデータ型はproduct typesと呼ばれ、以下の様なデータ型がこれにあてはまります

・tuple
・Pair
・Cons
・オブジェクト指向におけるクラス
たとえば、「X」がAとBとCの型の組み合わせからなる型であれば、Xは

type X = (A, B, C)
のように表現できます。
これを代数的な表現に変換すると

X = A * B * C
というように、型の掛け算として表現できます。ここでもなぜこのように表現して良いかは省略しますが、論理演算における「and」が「論理”積”」と呼ばれることとのアナロジーで直感的なイメージは掴んで頂けるのではないでしょうか。

リストの定義を代数的に変換してみる

再び、代数的データ構造を使って表現されたリストに戻ります。

List a = Nil | Cons a (List a)
代数的データ構造における表現ではリストはこのように定義されているのでした。
この表現において

・「|」はさきほど見たsum types：足し算として表現できる
・「Cons」はさきほど見たproduct types：掛け算として表現できる
ことを思い出してください。
このことを使って、リストの表現を代数的な表現に書き直してみます。

List a = Nil + a * (List a)
ですが、「Nil」がまだ邪魔です。

この定義におけるNilはsingletonつまり「空リスト」を表していました。
存在はしているが、最小限の情報量を持つ値、を表現すものとして「Nil」を「1」と表現することにします。
すると、さきほどのリストの定義は

List a = 1 + a * (List a)
と変換できます。
この式で定義されているのは「List a」です。
今は「List a」の正体を調べたいので、「List a」を「X」に置き換えて、代数のようにXの解を求めることを考えます。

X = 1 + a * X
ここまで変形すると、中学数学で見た簡単な数式のように見えてきます。

ところがここで問題があります。普通の数式であれば「a * X」を右辺に移行して

X - a * X = 1
のように変形して「X」を解いていくところです。

ですが、ここで扱っていいるのは、中学数学で扱っていたような数値ではなく「型」です。
型を「足し算」で表現できることはすでに見てきましたが、「引き算」による表現は導入できていません。

型を扱っている以上、「足し算」と「掛け算」だけを駆使して変形することで、X（List a）の正体を確かめることを考える必要がありそうです。

ですので、少し方針を変えてみます。

X = 1 + a * X
ここまでの変形はとくに問題ありませんでした。
今度は、右辺の「X」を「右辺全体」（もとのXの定義）で置き換えてみます。

X = 1 + a * (1 + a * X)
右辺の以下の部分について、分配法則が成り立つならば、括弧を展開できます。

a * (1 + a * X)
ここで、分配法則が成り立つとは

a * (b + c) = a * b + a * c
が成り立つということです。

これが成り立つことを確認するために、型表現に直してみます。

(a, b | c) = (a, b) | (a, c)
この式が表しているのは、
「a」と「b」または「c」とのproduct type (ex. tuple）は、
「a」と「b」のproduct typeまたは、「a」と「c」のproduct typeだと言うことです。

直感的にこれは問題なさそうですね。
つまり型における代数においても、分配法則は成立すると考えて問題なさそうです。

型の変換において分配法則を使えることがわかりました。

再度、変形途中だったリストの定義に戻ります。

X = 1 + a * (1 + a * X)
ここから右辺の括弧を展開したいのでした。分配法則を使って右辺の括弧を展開します。

X = 1 + a + a * a * X
ここでもう一度、右辺の中の「X」を「1 + a * X」（最初の「X」の定義）で置き換えます。

X = 1 + a + a * a * (1 + a * X)
再度、分配法則を使って括弧を展開します。

X = 1 + a + a * a + a * a * a * X
「X」を「1 + a * X」で置き換えて、分配法則を使って括弧を展開する、という変形を何度も繰り返すと

X = 1 + a + a * a + a * a * a + a * a * a * a +...
と変形できることがわかります。
この表現を再びもとの型表現に戻してみます。

List a = [] | [a] | [a, a] | [a, a, a] | [a, a, a, a] |...
型表現へと戻す際に

・「X」は「List a」を置き換えたものだったこと
・「1」は「Nil」を置き換えたもので、「Nil」は「空リスト」を表していたこと
・「a」のn個分のproduct typeは長さnのリストになること
・「足し算」は「|」を使ってsum typeに変換できること
を使いました。

ここまで変換すると、直感的にリストが何かを理解できます。

List aとは

・要素が0個の [] （空リスト）または
・要素が1つの [a] または
・要素が2つの [a, a] または
・要素が3つの [a, a, a] または
・要素が4つの [a, a, a, a] または
...
ということをList aの型定義を変形していくことで導くことができました。

これが代数的データ構造で表現されたリストの正体でした。無限長を取りうる、リストというデータ型を適切に表現できていることがわかります。

まとめ

プログラマに取って非常に身近な、リストというデータを具体例として、代数的データ構造を用いて、リスト型がどのように定義されるのかを見てきました。

sum typesやproduct typesをによって定義さる代数的データ構造は、通常の代数のように、「足し算」や「掛け算」で表現することができ、さらに分配法則も成り立つことから、その表現を変換していくことができました。
実際には、分配法則以外にも、結合法則や交換法則なども基本的には成り立つので、変換の仕方はこの記事で見たよりもより自由度が高いです。

このように、sum typesやproduct typesを使って*1表現されるデータ型は、まるで代数のようにデータ型の表現を変形することができるので、代数的データ構造と呼ばれています。

代数的データ構造とは何かのイメージを掴んで頂くとともに、代数的データ構造では

・無限の長さを取りうる「リスト」というデータの型を簡潔に表現できる
・その表現を「代数的」に変換することができる
・表現を変換することで、型に関する直感的なイメージを掴むことができる
といったところに面白さを感じていただけたなら、嬉しい限りです！