F# のDiscriminated Unionは代数的データ型などという、なんか難しそうな呼ばれ方をする。本当はレコード型も合わせてだが、それは良い。

Discriminated Unionは、近年のプログラム言語で割と多くの言語が持つ機能になった。 SwiftのEnumのassociated value、Kotlinのsealed class、RustのEnumなどはだいたいDiscriminated Unionと言って良いだろう。

だが、全部の言語が持つ訳でもなく、活用度も言語によって大きく異なっているように思う。 代数的データ型は思考方法やプログラムの構成方法と結びついて活用されるものなので、 Enumに値も持てます、という説明だと、いまいちそうした活用に結びつかない。 特にKotlinのようにより高機能なものだと、 かえって代数的データ型として使うためには一定のサブセットに意図的にとどまらないとうまく行かないため、 自然に習得出来る機能では無くなってしまっている。

言語機能自体はしょぼいもので大した事はない。 これらが代数的データ型と呼ばれるものです、というのはみんな一言書くが、その一言を書く人はそれが意味する事は説明しない。 そしてぐぐってみるとだいたい別の誰かが難しそうに解説していて意味が分からん。言語機能のしょぼさに対してなんか無駄に衒学的に思える。 英語でもalgebraic data typeとかでなんかやけに難しそうな単語だ。

言語を作っている側は代数的データ型の事を良く理解していて、 わかっている人がそう使えるように整備してくれているのだけれど、 わかっていない人に不必要に難しそうな印象を与えないように、 かえってこの辺の事が見えにくくなってしまっている言語が多い気がする。

という事で今回は代数的データ型について少し話をしてみたい。

代数的データ型とは

代数的データ型という時は、代数のように考えている所がある。 ここでいう代数とは、「掛け算と足し算」が定義されている世界という意味で、 集合の言葉でいう直積と和、つまりproductとunionという事になる。

直積は理論的にはタプルなんだが、プログラムの現実世界では構造体やレコード型も合わせて直積のようなもの、として考える。 ただ、anonymousな直積型が必要になる事はあるので、そうしたものがon the flyに作れる言語機能は必要だ。 タプルはこの条件を満たすので、代数的データ型をサポートする言語はだいたいタプルもある。

代数という言葉はようするに、 複数の型を使って新しい型を作るためのルールと言える。 それは8割くらいは構造体の事だ。 intを２つ持ったPointという型を作る、とか。

代数というのは、構造体が新しい構造体のフィールドになれる、というように、 このルールにしたがって作った新しい型は、また次の型の構成要素になれる、 という事を保証する仕組みである。 ようするにUnionと構造体で作る型は、また別の型の構成要素になれる、 という事だ。

これだけだと、当たり前過ぎて何を言いたいのか分からない。 難しい名前がついているが何も言っていないように見える。

代数的にデータ型を見るには、やってはいけない事が多々ある

代数的データ型があると、型を代数的に見る事が出来るようになる。 「見えるようになる」ではなくて「見る事が出来るようになる」というのがポイントで、 これは能動的にそう見ようとしないと、活用出来ない機能だ。 これが値を持つEnumという機能が与えられた時に、 活用度に大きな差が出来てくる所でもある。 sealedクラスで代数を見るのはさらに相当な訓練が必要だ。

代数的に見るためには、この機能をごく一部のサブセットに絞って使わないといけない。 幾つか思いつくのを挙げてみると以下のような感じだ。

  • プリミティブな型の合成で型を作っている
    • プリミティブな型が見えないといけない
    • プリミティブでない物があまり入ってはいけない
      • Fileとかコネクションとかとは相性が悪い
  • 特定の作られた型に特別な意味がありすぎてはいけない

プリミティブな型の合成だけで作られている、というのは凄く重要で、 これがいつでもプリミティブな型に分解出来て、それを再構成出来るという重要な性質につながる。 この特定のルールに従って再構成をしても特定のルールの中に必ずとどまる、というのが代数的という言葉の真意でもある。

これらの結果として、メソッドなどを作ってはいけないし、メンバを隠してもいけない。 この辺は代数的でない型の構成とは大きく異なる所なので、 そのように作らないとそうならない。 Unionの言語機能があるだけだと代数的データ型の威力がいまいち活かせない理由にもなっている。

Kotlinの言葉に翻訳するなら、プリミティブな型から構成されるメソッド無しのdataクラスと、 そのsealed classだけに限定する、という事になる。 相当に強い制限で、意図的に作らないとそうはならない事は誰にでもわかる。

これは例えば、ライブラリなどを使うとオブジェクトが帰ってきてしまう場合には困った事になる。 代数的データ型の世界といわゆるインピーダンスミスマッチが起きてしまう。 Fileとかコネクションのようなものをどうするべきか、 という難しさとも通じるものがある。 この辺とどう折り合いをつけていくかは人による所だと思う。

けれど、代数的データ型の威力を味わうにはこれらが入るといまいちだ。 だから最初のうちは、プログラムの中を、 これらが無い代数的データ型の領域と、それ以外の領域に分けてプログラムするのがいいんじゃないか。 最初のうちはこれらが無い所でリッチな型を作る事になれる必要がある。 リッチな型とは小さい型が大量に作られる事と思っておけばまずは良い。

ただここは人によって見解が分かれる所だろう。 レコードにファイルなどを入れても別に問題は無いので気にしない人もいるかもしれない。

代数的にデータ型を見るとは、SQLのテーブルのように見る事である

代数的にデータ型を見るご利益は、数学にあまり慣れていない人には分かりにくい。 だが、プログラマはそれを直接的に体感する場所がある。SQLのテーブルだ。

SQLはテーブルに対して操作を行う何かで、その結果としてテーブルが生まれる。 この結果として生まれるテーブルにも必ずSQLが使える。 これは非常に代数的な性質と言える。 実際Relational Algebraとかいうらしい事はみんな知ってる。

テーブルというのは、文字列とか数字とか基本的なデータをもとに、 それらを組み合わせて行が出来て、それが集まったもの、という事になっている。 また、そこから特定の用途に合わせてテーブルを変形する事が自由に出来る、 というのがSQLの強力さでもある。

代数的なデータ型を活かすのは、これと似たようにするのが良い。 プリミティブな型を集めて作られた型を作る。 これはSQLのテーブルのような何か（少し拡張したもの）になる。 これらのデータを用途に応じて変換して、新しいテーブルのような何かを作っていく。

新しいテーブルを作れるためには、いつももとのテーブルを構成要素に簡単に分解出来る必要がある。 そして構成要素から新しく作られたものが、もとのテーブルと同じ一級市民である必要がある。 特定のメソッドを使うためにはこのテーブルじゃないといけない、という事があると、 これがうまく行かない。

プログラムをSQLのように構成する

代数的データ型の威力を発揮するためには、プログラム自体をSQLのような部分と、 それ以外の部分にするのが良い。 そしてなるべく多くをSQLの部分でやるようにする。

プログラムを、テーブルを作り、テーブルを変換していく部分と、 目的のテーブルに対しての処理をする部分に分ける。 この目的のテーブルに対しての処理はなるべく自明な感じになるくらい、 最終的なテーブルが目的専用になるのが望ましい。

テーブルに対しての処理の部分はなるべく条件分岐なども無く、 単に何かをapplyしておしまい、のようになっているのが良い。 条件分岐などはその前のテーブルを作る方になるべく押し出す。

テーブルの中はプリミティブなデータとその合成だけにして、 Fileなどを使う所は最後のapplyする所になるべく押し出す感じに作る。 そうする事でテーブルを自由に作り直す自由が与えられて、 その中はバグりにくくわかりやすい世界に出来る。

このテーブル（のようなもの）を作って、テーブル（のようなもの）を変換していく部分を、 ここでは便宜上「SQL的な部分」と呼ぶ事にする。

SQL的な部分をリッチにしていく

プログラムを、SQL的な部分とそれ以外に分けて、なるべく多くのロジックをSQL的な方に持って行く、 というのが、このスタイルの基本的な方針である。

そしてSQL的な部分で必要な道具というのは、割とどのプログラムでも似通っている。 実際SQLは全てのアプリケーションで同じクエリを使っている。 むしろ同じ道具が使える、というのが、 代数的な世界をわざわざ作る理由でもある。

構成要素にバラして再構成するのに繰り返し使うのは、例えば以下のようなものになる。

  • パターンマッチでUnionをバラす
  • MapでSQLのSelectに相当する事をする
    • 複数のものから作る時にはZipしてMapする

この辺の道具を使って、一つのテーブルから別のテーブルへとどんどんテーブルを変換していくのがプログラムの大部分の作業となる。

さらに、「これらのような道具」をもっと増やしてリッチにしていく。 「これらのような道具」というのは具体的には、以下の２つになる。

  • 個々の型によらずに実行出来る変形の道具
  • 変形の内容によらずに特定の型で実行出来る道具

これらを揃えていく事で、ますますテーブル変形は快適になり、 問題に合わせて自由にテーブルを変更出来るようになるため、 機能変更やバグ修正も簡単になり、機能追加も容易になっていく。

構成要素が最終的にはプリミティブな事が保証されていて、 合成のルールが少数のものだけでそれぞれにバラし方や再構成の方法が用意されていると、 それらを組み合わせた一般的な道具というのが作りやすくなる。 この辺が世界をSQL的なものに分けるメリットでもある。

最初のうちは、SQLを参考に、SQLっぽい、集合っぽい道具にしていくと良いと思う。

テーブルを再構成出来るために必要な条件を再考する

プログラムをSQL的な部分とそれ以外に分けて、SQL的な部分をリッチにしていく、というのが基本方針という事を理解した所で、 SQL的なプログラムを構成するために必要な条件、 言い換えればテーブル的な何かとみなすために必要な条件を考え直してみる。

テーブルというのがプリミティブ型を合成した型（のデータ）である。

テーブルを変換して新しいテーブルを自由に作れるためには、以下を満たしている必要がある。

  1. テーブルからプリミティブな構成要素に自由に分解出来る必要がある
  2. 分解したプリミティブから新しいテーブルが自由に作れる必要がある
  3. （一時的なテーブルはいちいち型の定義をしなくてもon the flyに自由に作れて欲しい）

3はおまけなので、ここでは1と2を考え直す。

テーブルとテーブルの変換を自由に組み替えるためには、 テーブルをバラす事がどのテーブルでも自由に出来る必要がある。 これはようするに構造体のフィールドが全部publicでprimitive（またはその合成）だけでないといけない、 という事でもある。

そして新たなテーブルのコンストラクタはプリミティブ型（またはその合成）だけから作れる必要がある。

これらの条件は、意図的にそうしないとそうはならない。 これらを全部守ると、結局はF# などのレコード型とDiscriminated Unionと同じ何かになるし、 代数的データ型をサポートしている言語はだいたいこう書く「事が出来る」ようにはなっている。

これらはフィールドを隠して振る舞いをデータとセットにして定義していくスタイルとはとても相性が悪く、 昨今の言語は両方をサポートしている事が多いので、 意図的にどちらを使うかを選ばないと片方が使えない（だいたい代数的データ型の方が使われない）事になる。

SQL的な部分というのは、データをバラして再構成してバラして再構成して…を繰り返すプログラムになる。 だからデータはバラしやすく組み立てやすくなってないといけない。

プログラムのSQL的な部分を作るヒント

SQL的な部分を作るのはコツが要る。 特に既存の言語機能を「拡張」してこれらをサポートしていった言語では、 やってはいけない事が多く出来てしまう。

ここではより何でも出来る言語で生活している人がこれらをうまく活用出来るようになるために、ヒントを書いてみたい。

代数的データ型の学びにくさ

代数的データ型の学びにくさというのは、その言語機能を見た時に分からない事が無い所にあると思う。

知らない言語機能を見た時にそれを知らない、と認識するのは簡単な事で、 わかってない状態が認識できればそれを学ぶ事もやりやすいとは思う。 けれど代数的データ型は機能自体に難しい事が無く、 ご利益を得るためには「機能のごく一部に制限してそれだけを使う（プリミティブな型の合成型だけに制限する）」という必要がある。

より多くを知っている状態で、削る事で学びがある、 というのを認識するのはなかなか難しいし、「自分がわかっていない」と認識するのはさらに難題だ。 より難解な機能を理解している時に、Enumに値がついていてswitchがexhaustive checkしてくれる、 というだけの事が理解できないなんてありえない。 実際それを理解してない訳では無い。

だがそれだけでは代数的データ型のご利益は得られないし、代数的データ型という名前をつける意義は全く無い。

テーブルとSQLでプログラムのなるべく多くの範囲を構成する、 このSQL的部分にはたくさんの禁止事項があってそれらをやってはいけない、という事は、 プログラム言語のEnumの所の説明を見るだけでは分からない。

だからEnumの言語機能の説明の他に、SQL的な世界を作るというパラダイムというかスタイルを理解する必要がある、 という事をまず知っておく必要がある。

テーブルの変形、ツリーのtransform

代数的データ型とプリミティブ型で作られる世界というものをテーブルのようなもの、 と言ってきたし、実際テーブル的なものに収まっている場合は多い。 だが、たまにそれらに収まらない事がある。 そういう時はだいたいは、ツリーのようなデータになっている。

基本的にはツリーを変形して別のツリーを作る、というのを繰り返すのが、 より一般的な構造になる。

この構造の場合には、

  • ツリーのノードにメソッドをつけない
  • ツリーを副作用で変更せずに新しいツリーを作る
  • ノード型のようなものはなるべく作らない

というあたりを意識すると良い。

ノード型について補足しておくと、何か共通のノード型を作ってそれをwalkingするような関数などを整備していくのは、 そのノード型以外を構成するのを面倒にするので、 慣れるまではあまりやらない方が良い。 ノードとかツリーと思ってしまうよりも、 もうちょっとドメインに沿ったリッチな型でものを考える方が良い。

この辺は結構奥が深い所なので、最初にちゃんと理解するよりは、 最初のうちはあまり特定のノードを特別扱いせずに、 いろいろなツリーをどんどん変換していく感じでコードを書いてみるのが良いと思う。

興味がある人はThe “Recursive types and folds” Series · F# for Fun and Profitなどは詳しく書かれている。

とにかく、プログラムの大きなデザインを考える時に、 問題を「ツリーを変形して新しいツリーを作る、という風に解釈出来ないか？」と考えるのは、 SQL的部分を作る良い指針となる。

一度作ったツリーを大事に使いまわしてしまうんじゃなくて、どんどん新しいツリーにしてくように考えるのが良い。

テーブルで問題をモデリングする

問題をなるべくたくさんSQL的な部分に持っていくコツとしては、 コードで書かれているロジックを、テーブル的な方のモデリングで表現するように直していく、 というのがある。 このテーブルで問題をモデリングする、というのは、慣れが必要だ。

型で問題を表現する、というだけだと、広すぎてこの辺が正しく伝わりにくいと思う。

テーブル的な何かみたいな世界が心の中にあって、 その枠内で問題を表現するために頭をひねる必要がある。 この枠が代数という言葉で表現される本質なのだが、 最初のうちはとにかくある種の制約の中にとどまるというのを厳守していけば自然と分かってくると思う。

ifとかforで書かれているものを、テーブル的な構造になるべく置き換えていく。

モデリングは試行錯誤が重要

テーブル的な何かで問題をモデリングするためには、 テーブル的な何かをなんども再構成してみて、 問題がうまく表現出来るように試行錯誤する必要がある。

テーブル的な何かを何度も再構成してはやり直して試行錯誤する為には、 再構成が簡単で無くてはいけないし、再構成した結果がすぐにわからないといけない。

そのためには、テーブル的何かがコード上で狭い範囲に局所的に存在している必要がある。 具体的には行数が短い範囲にぎゅっと書かれていないといけない。

また、そこを変更するだけで変更した結果を理解出来る必要がある。 ビルドが通る必要は無いが、その局所的な範囲は直し漏れが破線で出たりsyntax highlightでカラーリングされるくらいは欲しい。

例えば昨日変更していたMatchExprの再構成の所は以下になる。MatchExpr type refactoring. · karino2/folang@f0096df このast.foの所をなんどもこねくり回していい感じになるように考える訳だ。

これが複数のファイルに散らばっていたり、同じファイルでも一画面とか二画面くらいに収まっていないと厳しい。 この辺がinterfaceと継承で同じ事をうやろうとするとどうもうまく行かない理由でもあると思う。 structは一行とか、せいぜい2〜3行で書けないと厳しい。 それが、このSQL的世界の全体でそうなっていないといけない。

この数十行の範囲で試行錯誤して問題をあーでもないこーでもないと表現の方法を試行錯誤するのが、 問題をなるべく多くSQL的な方に持っていくコツで、 そう出来るようにプログラムを構成しておく必要がある。 少なくともコンストラクタとかメソッドがここに入っていると厳しい。 ここだけでLSPがvalidと認めてくれるようなコードになっている必要がある。

if文の方まで問題を持っていかずに、テーブル定義の所で片付ける。 これが基本的な考え方になる。

表現はリッチなほど良くて、 どこまでこのテーブル定義の所で問題を表現出来るかは腕の見せどころであり、実力が出る所でもある。 「全ての問題をテーブル定義の所で片付けてやるぞ！」という意気込みでもって試行錯誤をしていく。

もちろんコードの方も合わせて直す必要はあるのだけれど、それは問題が片付いた「あと」にやる。 機械的にコンパイルエラーに従って直していくだけで、何も頭を使わずにやる作業となる。 この作業はかったるいだけなので、なるべく簡単に出来る方が嬉しくて、 この辺をどれだけ簡単に出来るか、が、言語のシンタックスなどが響いてくる所でもある。

この辺の話は、Designing with types: Making illegal states unrepresentableなどは参考になる。 この記事以外でも、「Making illegal states unrepresentable」は割といろいろな所で語られていて参考になる所。

小さな型を大量に作る

テーブル定義の所で問題を片付けるためには、 ここの表現がリッチである必要がある。

リッチな表現のためには、小さな型をたくさん作るのが良い。 小さな型は、通常のコードでいう所の変数名とか関数名に相当する役割を担う事になる。 コードの一部に名前をつけるように、テーブルの一部に名前をつける事に相当する。 可読性の為に型を作る。

大量の小さな型があると、ある型から別の型へ変換するコードを大量に書く事になる。 だからこの辺の言語サポートがある方が良く、近年の言語はこの辺のサポートが充実している。

言語機能だけでは無く、書く側もその変換が簡単になるように協力する必要がある。 これがSQL的な世界に持ち込んではいけないものがいろいろある理由でもある。

プリミティブ型と代数の力について認識する

プリミティブ型とその合成でいろいろな問題を表現したい。 この時どういう合成があれば良いだろう？

構造体とUnionがあって、その組み合わせで表現出来る範囲というのはかなり多くの問題が表現出来そうだ、 というのが一つの結論としてある。

また、その組み合わせだけで作られた世界というのは、お互いの変換やそれぞれで使えるツールを一般的に作りやすい程度には制約がある、 という事も経験的に知られている。

つまり、問題の多くを表現出来る程度にはパワフルでありながら、 いろいろなツールを作れる程度には限定的だ、というのが、 この代数的データ型のメリットとなる。

逆にこれでは出来ない事もたくさんある。あくまでこれで表現出来るのはピュアな限定的な世界であって、 プログラムを完成させる為にはこれで表現出来ない部分が必ずある。 例えば多くの言語では、interfaceと継承（や実装）によるポリモルフィックな振る舞いで、 これらよりも多くの事が表現出来る。

代数的データ型、もっと言えばそれを用いて実現出来るSQL的な世界というのは、 その内と外をはっきりと分けるその限定にこそメリットがある。

  • 多くの問題を表現出来るくらいには強力である
  • 多くのツールを作れるくらいには限定的である

という２つの側面が、代数的データ型の強みだ。 後者を理解するのは実体験が必要だと思う。

代数的データ型の威力を学ぶためには、SQL的な世界を限定的にする必要がある。 ファイルを開かずネットワークにpostせずifを使わずforを使わず変数に値を入れず、 こんな何もしない世界で一体何が出来るのか？ というくらいに制限の多い世界を作る。

この強い制約の中で今解こうとしている問題をどこまで表現出来るか？と考えるのが、 問題をどれだけSQL的な世界に持ってこれるのか？という事であり、 やってみるとこれが予想以上に多くを表現出来る。

近年の代数的データ型のサポートが広まっているのは、 みんなが試してみたら結構いろいろ出来た、という事なんじゃないか。

そういう訳で最初は半信半疑かもしれないが、一度凄く限定的なSQL的な部分を作るというスタイルでプログラムをしてみて、 これをどこまで広げられるのか頑張ってみると良いかもしれない。

関連記事

F# for Fun and Profitにはこの手の話が散らばっている。