「代数的データ型」という言葉をご存知でしょうか。

関数型言語を扱う機会がある方であれば触れることが多いかもしれませんね。

代数的データ型は、複雑なデータ構造を少ないコードで安全に扱うことができる型定義の一種で、最近ではJavaなどの手続型プログラミング言語でも代数的データ型を実現するための機能が追加されていたりします。

今回は、そんな代数的データ型について紹介していこうと思います。

(注意：記事中のコードは特に指定がない場合はTypescriptで書いています。)

1. 代数的データ型概要

「代数的データ型(Algebraic Data Type = ADT)」は代数学に由来するデータ構造で、以下に紹介する「直積型」と「直和型」の組み合わせによって表現されるデータ構造を指します。

同様の機能を持つデータ型として、言語によってはenum(Rust), 判別共用体(F#), タグ付共用体(Zen)などと呼ばれたりしますが、本記事では「代数的データ型」で統一したいと思います。

直積型
直和型
直積型×直和型＝代数的データ型

直積型

直積型(ProductType)は、いくつかの型をメンバーとして持つ型のことを表すデータ型です。

メンバーとして持つ全ての値の直積のパターン分のデータを表現することができます。

プログラミングにおいてはクラス、構造体に相当するデータ型ということができます。

type Circle = {
  radius: number;
　color: Color;
}

直和型

直和型(SumType)は、いくつかの型のうちの1つだけを保持する型のことを表すデータ型です。

集合論におけるORを表現するための型で、取りうる型が排他的(同時に複数の状態であることがない)となります。

また、プログラミングにおいては、Union、共用体に相当する型です。

type Color =
  | Red
  | Blue
  | Green

直積型×直和型＝代数的データ型

代数的データ型は、上記の直積型、直和型を組み合わせた型で、以下のような特徴を持っています。

取りうる型が排他的
いずれの型であるか判別が可能
いくつかの型をメンバーとして持つことができる

2. 代数的データ型のメリット

以上に述べた代数的データ型の特徴から、以下のようなメリットを挙げることができます。

複雑なデータ構造を少ないコード(パターンマッチング)で安全に扱うことができる
取りうる型の範囲を網羅的に表現することができ、実装の漏れを未然に防げる

パターンマッチング

代数的データ型をサポートしている言語では、パターンマッチングの構文が用意されていることも多いです。

パターンにマッチした型のみを想定して処理を記述することができるため、複雑な型を複数組み合わせた場合でも、安全に制御することができます。

また、if文などを用いた手続き的な分岐処理よりもシンプルに記述しやすく、コードが簡潔になります。

今回は、言語仕様として代数的データ型をサポートしているDartでサンプルのコードを書いてみました。

[パターンマッチングを使用したコード例]

静的な網羅性解析

代数的データ型は、取りうる型の範囲を網羅的に表現することができるため、分岐処理などを記載した際にパターンの処理漏れがある場合はコンパイル時点でエラーしてくれます。

そのため、静的にコードの網羅性を担保することができ、実装漏れなどを事前に防ぐことができます。

以下は、上述のDartコードのgetShapeInfo関数から”Circle”型に対するハンドリングを除外した場合のエラーです。

The type ‘Shape’ is not exhaustively mathced by the switch cases since it doesn’t match ‘Circle()’.
(型’Shape’は’Circle()’にマッチしないため、switch case によって網羅的にマッチしていない)

(疑問)サブクラス＋継承で代用できないの？

代数的データ型を用いることによって、代数的データ型が取りうる値の網羅性を担保しながらコーディングできるということがわかりました。

ところで、同じような網羅性のチェックは、クラスを用いた継承関係では表現できないのでしょうか？

下記は引き続きDartによる記載例です。

Dartでは “is” 演算子を使用するとオブジェクトの型チェックが可能で、Shape型のサブクラスであるTriangle, Square, Circle型にそれぞれマッチした処理を記述することが可能です。

ただし、親クラスであるShape型からは子クラスの範囲を把握することができないので、網羅性を担保することができません。

3. Typescriptでの実装例

Typescriptでは、言語レベルでは代数的データ型をサポートする構文はないものの、同等の機能を持つデータ型を定義することができます。

下記のコードでは、Adtという代数的データ型を作成する型定義を用意して、Shape型を定義しています。

Adt型は、型引数として渡されたオブジェクト型の各キーを識別子とした、オブジェクト型のUnionを形成します。

よって、左記の型定義は右記の型を定義するのと同等です。

getShapeName関数はShape型を引数にとって文字列で該当の矩形の情報を返してくれる関数です。

switch文を使って、各矩形のパターンごとに処理をしています。

Shape型は、Triangle, Square, Circleの3つのパターンの型をとりえます。

そのため、以下のように”Circle”のパターンを削除すると、網羅性チェックが働きコンパイルエラーが発生します。
(“Circle”がマッチするパターンの場合、返り値がundefinedになってしまう)

各caseブロックのスコープでは、それぞれの識別子にマッチする代数的データ型に型が絞り込まれているため、それ以外のパターンのプロパティを取り出すことはできません。

下記の例では、”Circle”にマッチしている場合は s = {type: “Circle”; radius: number} でることをTSCが推論してくれるため、width, heightなどのプロパティを参照しようとするとコンパイルエラーになります。

4. 代数的データ型の利用シーン

代数的データ型は、さまざまな場面で利用することができますが、イメージしやすい利用シーンとして以下の2つを例としてあげたいと思います。

木構造

代数的データ型が便利に使えるパターンとして個人的に鉄板だと思っているのは木構造です。

以下のサンプルコードでは、上述したAdt型を使用してNode, Leaf型を作っています。

insert関数はTree構造を再帰的に探索して新しいNodeを挿入するための関数ですが、木構造の末端(Leaf)に到達した場合(case “Leaf”のブロック)ではすでにLeaf型に推論されているので、誤ってvalue, left, rightプロパティを参照することがありません。

上記のコードを実行すると、以下のような木構造が生成されます。

複雑なパターンのUI 制御

また、以前私が関わった案件では、複雑なパターンを取りうるUIの制御に代数的データ型を採用しました。

添付した画像のように、ひとつの入力項目に対し、パターンにごとに入力項目数、表示するUI種別などが多様に変わりうるというUIだったのですが、代数的データ型を採用することによって以下のような問題を未然に防ぐことができました。

UIの表示パターンが追加された場合、パターンの実装が漏れてしまう
そのパターンでは想定していないプロパティの参照処理の記述により、エラーしてしまう

5. まとめ

代数的データ型は「直積」と「直和」の組み合わせ
言語機能として代数的データ型をサポートしている言語は増えてきている
代数的データ型を使うと、取りうる値の範囲を明確化でき、実装漏れをコンパイル前に検知できる

代数的データ型を用いることで、より柔軟・安全に型を制御できることがわかりました。

代数的データ型は関数型言語起源の型ですが、最近は様々な言語で採用されているので、ぜひ機会があれば触ってみてください。