代数的データ型とは

• 空気のようにあたりまえにあるデータ構造
• 圏論と関わりが多少ある
• 直積の直和
• パターンマッチとの組みあわせでつかわれる

直積型

直積型とは, c言語でいうところのstructです

struct product {
    int left;
    double right;
};

そこらじゅうにある

直和型

直和型とは, 雑にいうとc言語でいうところのenumです

enum sum { LEFT, RIGHT };

ただしこれは直和型のうち特殊なものになっています 本当はLEFTとRIGHTが型を持てます(上の例は型としてUnit型(void?)を持っていると見るべき)

疑似コード的ななにかで表わすとこうなります

enum sum { LEFT as int, RIGHT as double };

合法的な例

struct sum {
  int type;
#define TYPE_INT 1
#define TYPE_DOUBLE 2 
  union {
    int left;
    double right;
  } u;
};

そこらじゅうにあるのに, プログラミング言語のなかにはなかなかない…

そこらじゅうにあるのに, JSONにもない…

この直和型というのは, 開けてみたらどれかひとつの型が入っている感じを表わしています

これを開く操作に対応するものが, パターンマッチです

組みあわせると…

直和型のもととなる型は何でもよいです

直積を入れてもいいし, 直和を入れても, 自分自身の型を入れてもいいです

これを使って表わせるデータ構造は一般に木構造となります

つまりc言語で木構造は自然につくれないこととなっています(?)

JSONも木構造は自然につくれないこととなっています(??)

2分木の定義

enum tree { Leaf as int, Node as tree * tree };

これが使えない状況というのは手足がもがれたようなものです

ASTを表現するときもvisitor patternとかやっちゃったりして爆死したりします

最近になって直和型が入ってきた言語があります

public abstract record Tree;
public sealed record Leaf(int elem): Tree;
public sealed record Node(Tree left, Tree right): Tree;

これがC#9.0における代数的データ型です

一般的にsubtyping(オブジェクト指向の一部分)があれば, 直和型を表現することができます

つまり上の例でいうとTreeの部分型としてLeafを定義しています

こういう言語はつらいですが, なんとか使えます

まとめ

• 代数的データ型というイディオムがある
• 空気としてある
• みんなつかおう