TypeScript の Discriminated Union と Haskell の代数的データ型

この記事は 一休.com Advent Calendar 2024 の15日目の記事です。
予定より早く書き上げてしまったので、フライングですが公開してしまいます。

TypeScript の Discriminated Union (判別可能な Union 型) を使うと、いわゆる「代数的データ型」のユースケースを模倣することができます。一休のような予約システム開発においては「ありえない状態を表現しない」方針で型を宣言するためによく利用されています。

「あり得ない状態を表現しない」という型宣言の方針については以下の URL が参考になります。

Designing with types: Making illegal states unrepresentable | F# for fun and profit

このユースケースで Discriminated Union を使う場合、それは文字どおり「型の判別」のために使われます。この場合、判別の手がかりとなる「ディスクリミネーター」はただの分岐のためのシンボル程度の役割にしか見えないでしょう。しかしこれは、本機能の部分的な見方でしかないと考えています。

Haskell など、TypeScript のように模倣ではなく、型システムに代数的データ型がネイティブに組み込まれているプログラミング言語では、代数的データ型は新たなデータ型とデータ構造を宣言する一般的な手段です。代数的データ構造とパターンマッチを用いて、一般的なオブジェクトだけでなく、リストや木構造などのデータ型を構築・操作することができます。こちらのメンタルモデルから見ると代数的データ型こそが、データの構築と分解を型安全かつ表現力豊かに扱う基盤を提供するものであり、型駆動開発を支える根幹だと捉えられます。

本記事では TypeScript の Discriminated Union による代数的データ型の模倣についてまずその基本を確認し、その後 Haskell の代数的データ型の文法をみていきます。後者をみて先のメンタルモデルを獲得したのちに前者を改めて眺めてみることにより、新たな視点で TypeScript の機能を捉えることを目指します。

TypeScript の Discriminated Union (判別可能な Union 型)

TypeScript の Discriminated Union (判別可能な Union 型) を使うと、他のプログラミング言語でいうところの代数的データ型のユースケースを模倣することができます。Discriminated Union はディスクリミネーター (もしくはタグ) と呼ばれる文字列リテラルにより Union で合併した型に含まれる型を判別できるところから「タグつき Union 型」と呼ばれることもあります。

typescriptbook.jp

Discriminated Union をうまく使うと、アプリケーション開発において「存在しない状態」ができることを回避することが出来ます。存在する状態のみを型で宣言することで「存在しない状態ができていないこと」を型チェックにより保証することができます。書籍 Domain Modeling Made Functional などでも語られている非常に有用な実装パターンであり、一休が扱う予約などの業務システム開発でも頻繁に利用しています。

少しその様子を見てみます。

典型例として、何かしらのシステムのユーザー (User) について考えます。ユーザーには会員登録済みの会員 (Member) と、会員登録はしていないゲスト会員 (Guest) の区分があるというのは、よくあるケースでしょう。会員はユーザーID、名前、メールアドレスなどの値をもつが、ゲストはそれらが確定していない。

このとき ユーザーID が null なデータをゲストユーザーとして扱うという実装もあり得ますが、null チェックが必要になるし「ID が null なのがゲスト」という暗黙の仕様を持ち込むことになってしまいます。null に意味は与えたくありません。

そこで以下のように、Member と Guest を定義します。

type User = Member | Guest

type Member = {
  kind: "Member"
  id: number
  name: string
  email: string
}

type Guest = {
  kind: "Guest"
}

User 型のオブジェクトがあったとき、そのオブジェクトが Member 型なのか Guest 型なのかは kind プロパティの値によって判別できます。この kindプロパティが型の判別に使われるディスクリミネーター (あるいはタグ) です。

例えば、Member か Guest かでプレゼンテーションを分けたいというときは以下のように switch 文により Union 型を分解し、それぞれの型ごとに処理を記述することができます。

function showUser(user: User): string {
  switch (user.kind) {
    case "Member":
      return `ID: ${user.id}, Name: ${user.name}, Email: ${user.email}`
    case "Guest":
      return "Guest"
    default:
      assertNever(user)
  }
}

export function assertNever(_: never): never {
  throw new Error("Unexpected value. Should have been never.")
}

assertNever は網羅性チェックのためのイディオムで、これを置くことでナローイングの結果 User 型に含まれるすべての型に対し処理を定義したかを、コンパイル時にチェックすることができます。

以下の絵は実装途中の VSCode です。Member に対する処理は記述したが Guest に対する処理はまだ記述していない段階。コンパイラがエラーを出してくれています。

網羅性チェックによるコンパイルエラー

そして kind プロパティすなわちディスクリミネーターはリテラル型になっており、補完が効きます。

ディスクリミネーターの補完が効く

このように、Union により構造の異なる複数の型を合併しつつもディスクリミネーターによってそれを分解することができ、ナローイングによって型や網羅性チェックが効くことから、代数的データ型をエミューレトできていると言われます。ディスクリミネーターに基づいた switch 文での型の分解は、さながら「パターンマッチ」のように捉えられます。

仮に Discriminated Union を使わず、ゲストユーザーを「ID が null」で表現したとすると以下のように定義することになります。

type User = {
  id: number | null
  name?: string
  email?: string
}

この場合、たとえば ID が null にも関わらず name や email が null でない、という「ありえない状態」を表現できてしまいます。

これは Record 型が AND (積) に基づいたデータ構造の宣言であり、3 つのプロパティがそれぞれ「ある・なし」の 2パターンを取り、その積で合計 8 パターンの状態を取れてしまうことに起因しています。8パターンの状態の中には、実際にはあり得ない状態が含まれます。「ある・ なし」の分岐は ID に関してだけでよいのに、ほかの 2 つのプロパティまでそれに巻き込まれてしまった結果です。

Union 型は OR (和) に基づく合併なので「ID、名前、メールアドレスがある」 Member に、「プロパティがない」 Guest の状態を「足している」だけ。状態の積は取りません。よって合併しても状態が必要以上に増えません。

Making illegal states unrepresentable (ありえない状態を表現しない) というのはこういうことです。

実際のユースケース ··· 絵文字アイコンあるなしの表現

もうひとつ、我々の実際のアプリケーションでの実例の中から、簡単なものを紹介します。

我々の作ってる飲食店向け予約台帳システムには顧客管理の機能がありますが、顧客にタグ付けして分類することができます。タグは視認性向上のため絵文字が設定できるようになっています。

タグには絵文字が使える

タグを新しく作るときは絵文字を設定することができます。絵文字は設定しても、しなくても OK という仕様になっています。

絵文字は設定しても、しなくても OK

さて、このタグ用のアイコンである TagIcon のデータをどう管理するか、型を考えます。

「アイコンがない」というのを null で表現しようとしがちですが、「アイコンなし」という状態はそれはそれで存在する状態と考えることもできます。これを NoIcon という型にしてみます。「ない」を「ある」とみなすことで、状態を定義することができました。

結果、以下のように Union で表現することができるでしょう。こうして null に意味を持たせることを回避します。

type TagIcon = EmojiIcon | NoIcon

type EmojiIcon = {
  kind: "Emoji"
  symbol: string
}

type NoIcon = {
  kind: "NoIcon"
}

型を宣言したからには、この型の値を生成できるようにしましょう。コンストラクタ関数を定義します。このとき、型名と関数名を同じにする コンパニオンオブジェクトパターン を使うと良いです。

function EmojiIcon(symbol: string): EmojiIcon {
  return { kind: "Emoji", symbol }
}

function NoIcon(): NoIcon {
  return { kind: "NoIcon" }
}

少し話しが脱線しますが、EmojiIcon の symbol の文字列が確かに絵文字かどうかをチェックすることで、値の完全性をより厳密にすることができます。

function EmojiIcon(symbol: string): Result<EmojiIcon, ValidationError> {
  return symbol.match(/\p{Emoji}/gu) ? ok({ kind: "Emoji", symbol }) : err(new ValidationError('Emoji ではありません'))
}

プロダクトの実装ではそうしていますが、例外をどう扱うかなど本稿とは関係のないトピックが出てきてしまうので以降省略します。

もとい、これで型、つまりは値の構造の定義とその生成方法を定義できました。あとは先にみた User の例のように、アイコンが絵文字か・絵文字なしかで処理を切り分けたいときは kind プロパティでパターンマッチ的に分解すればよいです。

function toHTMLIcon(icon: TagIcon): string {
  switch (icon.kind) {
    case "Emoji":
      return icon.symbol
    case "NoIcon":
      return ""
    default:
      assertNever(icon)
  }
}

export function assertNever(_: never): never {
  throw new Error("Unexpected value. Should have been never.")
}

追加の仕様で絵文字だけでなく、オリジナルのアップロード画像も扱いたいとしましょう。その場合は Union に新たに ImageIcon 型を追加すればよいでしょう。

type TagIcon = EmojiIcon | NoIcon | ImageIcon // ImageIcon を新たに併合

type EmojiIcon = {
  kind: "Emoji"
  symbol: string
}

type NoIcon = {
  kind: "NoIcon"
}

// これを追加
type ImageIcon = {
  kind: "Image"
  url: string
  name: string
}

ImageIcon åž‹ã‚’ Union に追加すると、パターンマッチしている分岐で網羅性チェックが働き、期待通り、コンパイルが通らなくなります。型に応じた処理を追加します。

function toHTMLIcon(icon: TagIcon): string {
  switch (icon.kind) {
    case "Emoji":
      return icon.symbol
    case "NoIcon":
      return ""
    case "Image": // これを追加しないとコンパイルエラー
      return `<img src="${icon.url}" alt="${icon.name}" />`
    default:
      assertNever(icon)
  }
}

実際に作った型を値として使う場合は、以下のような使い方になります。

const icon1 = EmojiIcon("🍣")
const icon2 = NoIcon()
const icon3 = ImageIcon("https://example.com/image.png", "Example Image")

console.log(toHTMLIcon(icon1)) // 🍣
console.log(toHTMLIcon(icon2)) //
console.log(toHTMLIcon(icon3)) // <img src="https://example.com/image.png" alt="Example Image" />

Discriminated Union により型を構造化し、コンパニオンオブジェクトパターンで生成を実装し、switch 文によるナローイングでパターンマッチ的に分解を実装しました。null を使わず NoIcon という状態を導入したおかげで見通しよく、静的検査を有向に活用しながら実装できました。

ディスクリミネーターは、ただの判別用のシンボル?

ここまででも十分、Discriminated Union の有用性が確認できますが、仕組みとしてはオブジェクトのプロパティに kind など適当なプロパティ名でディスクリミネーターを忍ばせた程度にも見えます。

TypeScript レイヤではナローイングによって型チェックが効くなど上手いこと機能していて座布団一枚! という感じ (?) もありますが、JavaScript のレイヤーでみるとただオブジェクトのプロパティの文字列で分岐しているだけのようにも思えて、そんなに本質的な事柄なのか? とも思えてしまいます。

Discriminated Union が表現できるものは、この程度のものと思っておけばいいのでしょうか? いいえ、という話を続けてみていこうと思います。

Haskell のデータ型宣言

代数的データ型を「模倣できる」 TypeScript ではなく、代数的データ型を型システムにネイティブで搭載しているプログラミング言語、たとえば Haskell で同じ実装がどうなるのか、見てみましょう。

以下のように実装できます。

import Text.Printf (printf)

data TagIcon = NoIcon | EmojiIcon String | ImageIcon String String

toHTMLIcon :: TagIcon -> String
toHTMLIcon NoIcon = ""
toHTMLIcon (EmojiIcon symbol) =  symbol
toHTMLIcon (ImageIcon url name) = printf "<img src=\"%s\" alt=\"%s\" >" url name

main :: IO ()
main = do
  let icon1 = NoIcon
      icon2 = EmojiIcon "🍣"
      icon3 = ImageIcon "https://exmaple.com/image.png" "Example Image"

  putStrLn $ toHTMLIcon icon1
  putStrLn $ toHTMLIcon icon2
  putStrLn $ toHTMLIcon icon3

TypeScript での実装に比較すると分量がかなり短くなっています。とは言え、コードが短いかどうかはあまり重要ではありません。より詳細に見てみましょう。

まず、TypeScript のケースとは異なりコンストラクタの明示的な実装がないことに気がつきます。

そして toHTMLIcon 関数の引数でパターンマッチをしていますが、TypeScript のディスクリミネーターに相当するのは文字列リテラル的な値ではなく NoIcon EmojiIcon ImageIcon などのシンボルです。Haskell ではこれを「データコンストラクタ」と呼びます。データコンストラクタにより TagIcon 型の値を分解することができています。

TagIcon 型の宣言にもデータコンストラクタが使われています。データコンストラクタはデータ型の形状や構造を定義するものとしても使われます。

data TagIcon = NoIcon | EmojiIcon String | ImageIcon String String

そして値を生成するときも、データコンストラクタが使われています。

  let icon1 = NoIcon
      icon2 = EmojiIcon "🍣"
      icon3 = ImageIcon "https://exmaple.com/image.png" "Example Image"

このように Haskell ではデータコンストラクタが「タグ付き Union」におけるタグ相当ですが、データコンストラクタは型に基づいた値の分解、データ型の構築、値の生成と、データ型にまつわる操作を提供するものになっています。

TypeScipt で Discriminated Union とコンパニオンオブジェクトパターン、switch 文 と複数の文法を組み合わせて模倣していた機能が、Haskell ではデータコンストラクタという仕組みによって、より密結合された、統一的なかたちで実現されています。これが Haskell における代数的データ型（Algebraic Data Types, ADT）の特徴です。

そして Haskell では新しい型とデータ構造を定義する基本的な方法が、この data キーワードによる宣言です。 ···ということは、このデータコンストラクタを中心とした代数的データ型の文法でより複雑なデータ構造とその型を宣言することができることを意味します。

代数的データ型でより構造的なデータ型を扱う

永続データプログラミングと永続データ構造 - 一休.com Developers Blog で紹介した、二分木 (による永続データ配列) の実装を見てみましょう。実装詳細には立ち入らず、雰囲気だけみてもらえばよいです。

-- データ型の宣言
data Tree a = Leaf a | Node (Tree a) (Tree a)

-- 木を根から走査。パターンマッチと再帰で辿っていく
read :: Int -> Tree a -> a
read _ (Leaf x) = x
read i (Node left right)
  | i < size left = read i left
  | otherwise = read (i - size left) right

write :: Int -> a -> Tree a -> Tree a
write _ v (Leaf _) = Leaf v
write i v (Node left right)
  | i < size left = Node (write i v left) right
  | otherwise = Node left (write (i - size left) v right)

size :: Tree a -> Int
size (Leaf _) = 1
size (Node left right) = size left + size right

fromList :: [a] -> Tree a
fromList [] = error "Cannot build tree from empty list"
fromList [x] = Leaf x
fromList xs =
  let mid = length xs `div` 2
   in Node (fromList (take mid xs)) (fromList (drop mid xs))

main :: IO ()
main = do
  let arr = fromList [1 .. 8 :: Int]

  print $ read 3 arr -- 3

  let arr' = write 3 42 arr

  print $ read 3 arr' -- 42
  print $ read 3 arr  -- 3

重要なポイントとしては、コメントに書いたとおり (1) 完全二分木の木構造を data キーワードのみで宣言していること、(2) 木の中から目的のノードを探すにあたりパターンマッチで分解しながら走査していること、の 2 点が挙げられます。

データ型の宣言を改めてみてみましょう。

data Tree a = Leaf a | Node (Tree a) (Tree a)

Tree 型が再帰的に宣言されているのがわかります。再帰データ型が宣言できるため、木のようなデータ構造を代数的データ型により構築することができます。

さて、こうして木を実装する例をみると代数的データ型は、冒頭でみたような、ただの型を合併して判別する機能というものではなく、まさに「データの型と構造を構築するためのもの」だというのがわかります。

同様にリスト構造の List 型を自前で実装してみましょう。リストの走査として先頭に要素を追加する cons 関数と、リストの値それぞれを写像する mapList 関数も実装してみます。

data List a = Empty | Cons a (List a) deriving (Show)

empty :: List a
empty = Empty

cons :: a -> List a -> List a
cons = Cons

mapList :: (a -> b) -> List a -> List b
mapList _ Empty = Empty
mapList f (Cons x xs) = Cons (f x) (mapList f xs)

-- テスト出力
main :: IO ()
main = do
  let xs = cons 1 (cons 2 (cons 3 empty))

  print (mapList (* 2) xs) -- Cons 2 (Cons 4 (Cons 6 Empty))

先の二分木に同じく、data キーワードにより再帰データ型を定義してリストのデータ構造を構築しています。mapList 関数ではパターンマッチを用いてリストを走査し、リストが保持する値に写像関数を適用しています。データコンストラクタが、データ構造の構築とパターンマッチによる分解双方に利用されていることがわかります。

このように Haskell のデータ型は「値がどのように構造化され、意味づけられるか」を定義する手段です。データコンストラクタはその手段を提供し、構築と分解という双方向の操作を統一的に扱えるようにします。

この観点に立つと、データ型とデータコンストラクタの役割は次のように整理できそうです。

1. データ型は、プログラム内の「概念モデル」を定義する
2. データコンストラクタは、そのモデルの構築ルールを提供する
3. パターンマッチによる分解は、そのモデルを解析し操作する方法を提供する

TypeScript に同様のメンタルモデルを持ち込む

Haskell のデータ型の宣言をここまで見てから、改めて TypeScript に戻ってきましょう。代数的データ型に対するメンタルモデルが大きく更新されているはずです。

その視点で、改めて Discriminated Union よる代数的データ型の模倣を見てみましょう。「 kind プロパティは分岐目的のもの」ではなく Haskell 同様 「データ型を構築、分解する手段」として捉えることができるのではないでしょうか?

さて、TypeScript の型システムも Haskell 同様、再帰データ型は宣言できます。先の Haskell で実装したリストを、TypeScript で、これまでみた Discriminated Union、コンパニオンオブジェクトパターン、switch 文によるパターンマッチのイディオムで、実装してみます。

type List<T> = Empty | Cons<T>

interface Empty {
  kind: "Empty"
}

interface Cons<T> {
  kind: "Cons"
  head: T
  tail: List<T>
}

function Empty(): Empty {
  return { kind: "Empty" }
}

function Cons<T>(head: T, tail: List<T>): Cons<T> {
  return { kind: "Cons", head, tail }
}

type map = <T, U>(f: (a: T) => U, xs: List<T>) => List<U>

const map: map = (f, xs) => {
  switch (xs.kind) {
    case "Empty":
      return Empty()
    case "Cons":
      return Cons(f(xs.head), map(f, xs.tail))
    default:
      assertNever(xs)
  }
}

export function assertNever(_: never): never {
  throw new Error()
}

const xs: List<number> = Cons(1, Cons(2, Cons(3, Empty())))
console.log(map(i => i * 2, xs))

以下が実行結果です。Discriminated Union で構造化されたリストと、各値が写像により倍化された結果が得られています。

$ deno run -A list.ts
{
  kind: "Cons",
  head: 2,
  tail: {
    kind: "Cons",
    head: 4,
    tail: { kind: "Cons", head: 6, tail: { kind: "Empty" } }
  }
}

TypeScript でも無理なく、再帰データ構造を実装できました。

比較してみると TypeScript による代数的データ型は模倣だけあって、Haskell ほど簡潔に表現することはできません。一方で、それをどのようなメンタルモデルで捉えるかは、プログラミング言語の文法には左右されないでしょうから、Haskell のそれ同様に捉えてもよいでしょう。簡潔性は及ばないものの、機能的にはさほど遜色のない実装をすることができました。もちろん、より複雑なパターンマッチを要するものやランタイム性能の影響などで Haskell 同等とまではいきませんが。

目論見どおり、TypeScript の Discriminated Union に対する印象をアップデートすることができたでしょうか? できていることを願います 😀

実務で Discriminated Union を用いて再帰データ構造を宣言する、という機会はあまりないとは思いますが、それがただの Union で併合された型を判別できるものと小さく捉えるのではなく、本稿でみた通りデータ型の構築と分解の観点で捉えておくと視点が拡がるでしょうし、より広範囲に適用していってよいものだという確証が得られるのではないかと思います。

余談

TypeScript と Haskell を比較する記事を、過去に幾つか書きました。

• TypeScriptでどこまで「関数型プログラミング」するか ─ 「手続き Haskell」から考察する - 一休.com Developers Blog
• 永続データプログラミングと永続データ構造 - 一休.com Developers Blog

TypeScript の型システムは JavaScript の上に後付けされたものということもあり、非常にプラクティカルで便利である一方、個人的には、やや散らかっていてその全体像や各機能の本質を掴みにくいと感じています。Haskell など表現に妥協の少ないプログラミング言語と比較し、相対化することでより深い理解に繋がることは多いです。

雑にまとめると Haskell やれば TypeScript 書くの上達する

— naoya (@naoya_ito) 2024å¹´11月16æ—¥

Enjoy !