クラウド温泉3.0 (2) / 代数的データ型

クラウド温泉3.0@小樽のセッション「Monadicプログラミング・マニアックス」で使用するスライドのネタ検討その2です。

関数型プログラミングの基本構成要素の一つに代数的データ型があります。Wikipediaによる定義は以下です。

• 代数的データ型(Wikipedia)

ボク自身は計算機科学や数学の素養がないので、Wikipediaの定義が厳密には何を指しているのか十分に理解ができているとはいえないのですが、ボクと同じ立ち位置にいる非計算機科学系のプログラマの方には、ボクがプログラミング時に使用している非公式な理解が不正確なものであっても有益ではないかと思います。

その前提で、以下でScalaでの代数的データ型について考えます。

非公式な理解

ボクが代数的データ型を意識するときは、以下の定義を念頭に置いています。

• 直積の直和の総和

直積は、「A×B×C」というように記述する複数の要素を組にしたものです。Scalaではタプルが直積の代表的な記述方式です。

直和は、「互いに交わらない、つまり共通部分が空集合であるような二つの集合の和集合」です。「A∪B」でAとBでダブリがない場合が該当します。ScalaではEitherが直和の代表的な記述方法です。

「直積の直和」は以下のようにイメージしています。

T = (A × B × C) ∪ (D × E)

直和は2つの和集合なので、これを複数の集合の和集合に拡張して考える必要があります。ここでは、これを総和と表現しています。

「直積の直和の総和」は以下のようにイメージしています。

T = (A × B × C) ∪ (D × E) ∪ (F × G × H)

「直積の直和の総和」であるTは以下の意味を持ちます。

• Tは(A × B × C)の組、(D × E)の組、(F × G × H)の組のいずれかで、それ以外の値は持たない。

直和であることでダブリがないことに加えて「それ以外の値は持たない」となるわけですが、この性質が本質的に重要です。「それ以外の値は持たない」ので、選択処理で抜け漏れが発生することが絶対にないことを保証することができます。Scalaの場合は、コンパイル時にmatch式に対して「match is not exhaustive!」という警告を出すといった動きになります。

関数型プログラミングとオブジェクト指向プログラミング

最近のプログラミング言語は、関数型言語もオブジェクト指向言語も相互に影響を受けて便利そうな機能は同様に使えることが多く、境界線は曖昧です。例題レベルの簡単なプログラムだと、どちらも同じようにコーディングできることも多いでしょう。

このため、関数型プログラミングとオブジェクト指向プログラミングの本質的な違いは何かというのはかなり難しい問題ですが、JavaやScalaでプログラミングしている中で、情況証拠的に分かってきたのは「インヘリタンスの有無」がその本質ではないかということです。これは「動的に解決される多相性の有無」ということもできます。言葉を変えると、コンパイル時に抜け漏れが起きないことを保証できるのが関数型言語で、保証できないのがオブジェクト指向言語という表現もできます。

逆に、静的に解決される多相性は(オブジェクト指向でも有効ですが)関数型言語の守備範囲で、型クラスがこの代表的な機能になります。

もちろん、抜け漏れがあるオブジェクト指向言語が劣るとういうことではなく、動的にシステムを拡張できるという重要な性質の裏返しということです。プラグインをコンポーネントとして追加してアプリケーションを拡張する、といったアプローチはオブジェクト指向ならではということですね。

まとめると、オブジェクト指向では型(クラス)に毎に適用するロジックを切り替える処理はクラスのインヘリタンスによる多相性で実現します。これを関数型では以下のいずれかで実現します。

• 代数的データ型に対する選択
• 型クラス

型クラスはちょっとビッグな機能で日々のプログラミングで気軽に定義して使うものではないので、ざっくりといってしまうと、以下のように考えることができます。

• オブジェクト指向はインヘリタンス
• 関数型は代数的データ型で選択

そう考えていくと、代数的データ型は関数型プログラミングをする上で、かなり重要な機能であることが分かります。また、Scalaで関数型プログラミングを行う場合は、インヘリタンスは使わず「代数的データ型で選択」に持っていくことが正しい作法ということになりそうです。

Scala

と、ここからScalaの実装に入りたいところですが、長くなってしまったので次回にします。