Haskellの代数的データ型
Haskellの学習で直和型や直積型など、代数的データ型を理解すれば良いという話がありました。
本物のHaskellを書くには何が必要ですか？ この言語の中核は非常に単純です。 作成方法と使用方法を理解している場合
- 純粋な関数と値
- パターンマッチング
- 直和型と直積型
- 副作用を作るためにIOをつなぐ方法
直和型とか直積型というデータ構造については、「入門Haskellプログラミング」という本でも説明されています。
UNIT 3 型によるプログラミング
LESSON 16 直積型と直和型
補足情報を得るため、ネットでも検索してみました。
代数的データ型（英: Algebraic data type）とはプログラミング、特に関数型プログラミングや型システムにおいて使われるデータ型である。
基本的な代数データ型としては、多くの関数型言語において、言語組み込みのリスト型が用意されており、空リストのためのコンストラクタに相当するリテラルと、追加したい要素と残りのリストを引数に取るコンストラクタ（Lispのcons）に相当する、中置演算子風のコンストラクタ（ ":" など）が言語組み込みで用意されている。
代数的データ型の特殊な例として、直積型（1つのコンストラクタだけを持つ）と列挙型（引数なしの多くのコンストラクタを持つ）がある。
理論
集合論において代数的データ型と等価なものとして直和がある。この集合の各元はタグ（コンストラクタと等価）とそのタグに対応する型のオブジェクト（コンストラクタの引数と等価）で構成される。
一般に代数的データ型は直積型の総和であり、再帰的に定義されることもある。
各コンストラクタは直積型のタグとなって他と区別されるか、1つしかコンストラクタがない場合は、そのデータ型自体が直積型となる。
さらにコンストラクタの引数の型が直積型の要素となる。
引数のないコンストラクタは空に対応する。
Haskell や OCaml などの言語を特徴付けるものとして，代数的データ型 (Algebraic Data Type; ADT) の存在は無視できないだろう．その有用性ゆえに，近年では新たな言語の策定の際にその概念が輸出され，Rust や Swift などの言語にも採用されている．
| 数学 | プログラム (Haskell) |
|---|---|
Void |
|
() |
|
Bool |
|
Either a b |
|
| 特に |
Maybe a |
(a, b) |
|
a -> b |
以下の3つを合わせて代数的データ型と呼びます。
- 列挙型（他言語のenumに相当）
- 直積型（他言語のstructに相当）
- 直和型（他言語のunionに相当）
1. 代数的データ型とは
代数的データ型（algebraic data type）とは，図のように木構造で表現される値からなるデータ型のことです．
配列のような一部の例外を別とすれば，Haskell で取り扱うあらゆるデータ型は代数的データ型です．
もう少しきちんと説明すると，代数的データ型は項（term）の形で表されるデータの集合を定義するデータ型です．
Maybe 型もオーソドックスな代数的データ型のひとつです．
data Maybe a = Nothing | Just a
簡潔性の他の要因としてはOCamlにある型の表現の表記にあります。この表記の中心にあるのは代数データ型です。代数データ型とは積または和で新しい型を作ることが出来るシステム内で得られるものです。
直積型は2つの中ではよく知られている方です。タプル、レコード、構造体、オブジェクトはすべて直積型の例です。直積型は異なる型の複数の値を1つの値に結合します。これらは数学的に成分のデカルト積に対応するので直積型と呼ばれています。
直和型は成分の直和に対応して、複数の可能性を表すのに使われます。直和型が使われるのは複数のもの（aとbとc）を同時に表現したい時に使われます。直和型は（不格好ではあるけど）Javaでサブクラスを使うといった具合に、オブジェクト指向でモデル化出来ます。またCでは共用体として登場します。しかしほとんどの言語で直和型を安全に扱う上での型システムにおけるサポートは、驚くほど弱いのです。
代数的データ型 (algebraic data type) は直積と直和と再帰によって構成される型である。
代数的データ型のおさらい
data Bool = True | False
コンストラクタ
data Either a b = Left a | Right b
コンストラクタの引数
図の下側では、左側にオブジェクト指向の世界、右側に関数型の世界を配置しています。関数型プログラミングの基本中の基本は副作用がないことです。左側が副作用のある世界、右側が副作用のない世界となります。
関数型の世界では、副作用がない計算を実現するために、以下の3つの機能を使います。
- 関数
- 代数的データ型
- 永続データ構造
オブジェクト指向で値オブジェクト(value object)として扱っていたものは、代数的データ型に、データ構造は永続データ構造に変換した上で使用します。
代数的データ構造は、代数的な計算に適したデータ型です。
代数的構造(algebraic structure)は代数学の基本概念です。
結合律(associative law)、交換律(commutative law)、分配率(distributive law)というと難しそうに感じますが、法則そのものは小学校の算数に登場するもので誰でも知っていることです。
代数学で重要なのは、算数で使用するこれらの基本概念が数値計算以外の任意のドメインに対して適用することができるように抽象化を行っていることです。これらの基本概念を適用するための条件や計算方法を定めています。
このため、代数構造的デザインパターンをアプリケーションが定義した任意の代数的データ型に適用することによって、代数が提供する理論体系を適用することができるようになります。
data List a = Nil | Cons a (List a)
上記のデータ型は、代数方程式から導き出されている。
そこで、このようなデータ型を、特に、代数的データ型と呼ぶ。
上記のデータ型は、また、良く知られているリストの定義である。
下図に示すように、リストの定義が代数方程式から導き出される。
何とも面白い変換だと思う。
まとめ
- 代数的データ型は、数学の代数の成果（圏論、群論など）を取り込んで使える。
- 代数的データ型は、木構造で表現される値からなるデータ型のこと。
- 代数的データ型は、副作用がない計算を実現するために使える。
- 代数的データ型は、算数の基本（結合律、交換律、分配律）で考えることができる。
- 代数的データ型は、代数方程式から導き出される。
代数的データ構造の特徴と使い方を理解して、型のメリットを活用した関数型プログラミングを実現したいです。
