関数型プログラミング Ch7 代数的データ型と関係

代数的データ型と関係 (集合論)

Haskell のデータ型はすべて 代数的データ型 です. 代数的データ型には, 列挙型, 直積型, 直和型 があり, 構文として レコード構文 などが存在します.

代数的データ型は文字通り, 数学における代数の構造を参照したデータ型であり, 代数的な定義と対応させることで様々なことが可能となります. 代数学を理解するためにはまず, 集合論の基礎を理解している必要があります. 本章では, 集合論と対応させる形で, 代数的データ型とは何であるかを理解することを目指します.

本章は 2 部構成です. 前半 では型を集合とみなし, 集合を 作る 道具 (列挙・直積・直和・再帰) と Haskell のデータ型定義を対応させます. 後半 では集合の 間 のつながり — 関係, そしてその特別な場合としての関数・同値関係・順序関係 — を扱います. 後半は次章の型クラス (Eq・Ord) の数学的な土台になります.

本章の地図として, 集合論と Haskell の対応をまとめておきます (それぞれ対応する節で説明します).

集合と列挙型

Haskell ではデータ型を集合と みなすこと ができます. Haskell の型はあくまで型であり, 厳密には集合ではありません. また, 後の節で出てくるリストを使った 内包表記 などの 集合論的な書き方 も数学における集合ではありません. あくまで類似したものです.

しかし, Haskell を集合とみなすことで, 関数型プログラミングや, 代数的データ型の意味がより直感的に理解できるようになります. しばらく, 集合論と Haskell の対応について考えてみましょう.

集合の細かな定義は置いておいて, この講義では取り敢えずこのくらいの認識で問題ありません. しかし, ただのモノの集まりではなく, 特定のモノがそこに属するかどうかを判定できる必要があるので注意が必要です.

例えば, ｢頭の良い人の集合｣のようなものは, ｢頭が良い基準｣が人によって異なるので, 集合とはみなせません.

ノーベル賞受賞者の集合, フィールズ賞受賞者の集合, メンサ会員の集合, XX模試の偏差値が70以上の人の集合, 特定の科目で85点以上取った人の集合, など, 誰でも判別可能な定義が必要です.

集合の表記法には, 外延(的)表記 及び 内包(的)表記 という2通りが存在します.

外延表記とは, 特定の集合に含まれる要素を全て記述する方法です. 私が過去に飼ったことのある犬の種類の集合を MyDogs という名前で呼ぶと, MyDogs に属するモノたちを記号 { } を使った外延表記によって以下のように書くことができます.

\begin{align*} MyDogs = & \{ GoldenRetriever \\ &, BlackRetriever \\ &, ShetlandSheepdog \\ &, StandardPoodle \\ &, Beagle \} \end{align*}

このとき, GoldenRetriever や, ShetlandSheepdog は MyDogs の 要素 であるといい, 要素が特定の集合に属するとき,

GoldenRetriever \in MyDogs の様に書きます. 要素に属さないことは Chihuahua \notin MyDogs と書きます.

集合には順番は関係ないため, \{x,y\}=\{y,x\} となります. また, 一つの集合に同じ要素は2つ以上属することができず, \{x,x\} のような集合は定義できません.

Haskell において, 集合に属する要素をすべて書き出す (列挙する) データ型を 列挙型 として定義できます. データ型の宣言は, data のあとに続いて, データ型の名前(型構築子) を書き, = の後ろにその 中身(コンストラクタ/データ構築子) を書きます. 型構築子やデータ構築子は, 大文字の英字で始めるのが規則です.

data MyDogs = GoldenRetriever
            | BlackRetriever
            | ShetlandSheepdog
            | StandardPoodle
            | Beagle
            deriving Show

data My🐶   = Pゴールデンレトリーバー
            | Pブラックレトリーバー
            | Pシェットランドシープドッグ
            | Pスタンダードプードル
            | Pビーグル
            deriving Show

deriving Show はコンストラクタを文字列に変換する関数 show を自動で導入するための記法です. 自分で定義することも可能ですが, 詳細に関しては後ほど扱います.

deriving Show を入れていない状態で

print GoldenRetriever

などを実行すると, 以下のエラーがでますが, deriving Show を追加することで, 表示することが可能となります.

ghci> :{
ghci| data MyDogs = GoldenRetriever
ghci|             | BlackRetriever
ghci| :}
ghci> print GoldenRetriever

<interactive>:17:1: error: [GHC-39999]
    • No instance for ‘Show MyDogs’ arising from a use of ‘print’
    • In the expression: print GoldenRetriever
      In an equation for ‘it’: it = print GoldenRetriever
ghci> :{
ghci| data MyDogs = GoldenRetriever
ghci|             | BlackRetriever
ghci|             deriving Show
ghci| :}
ghci> print GoldenRetriever
GoldenRetriever

なお, print の実装は

print :: Show a => a -> IO ()
print x = putStrLn (show x)

となっています.

要素が一つも属さない集合を 空集合 といい, 記号 \phi または \{\} によって表されます. Haskell では空集合を表すデータ型として Data.Void に定義された Void が存在します. データ型として ボトム型, 記号では ⊥ で表される場合もあります.

Void と同じ値を持たないデータ型は, コンストラクタを記述しないことで自分で実装することもできます. 例えばある人が犬を今までに一匹もかったことがない場合を想定し, その人の飼った犬の集合を EmptyDogs と呼ぶことにすると, \mathrm{EmptyDogs} = \phi となり, データ型としては以下のように定義されます. 値が存在しない空集合と対応していることが分かります.

data EmptyDogs

someFunc :: Int -> Int
someFunc = undefined

main :: IO ()
main = print (someFunc 1)   -- 実行時エラー: Prelude.undefined

単一の要素だけが存在するデータ型として Unit 型も準備されており, () のような空のタプルとして表されます.

-- 実行例
main :: IO ()
main = do
    print $ isWeekend Sunday    -- True
    print $ isWeekend Monday    -- False
    print $ isWeekend Saturday  -- True
    print $ nextDay Friday      -- Saturday
    print $ nextDay Saturday    -- Sunday

data Weekday = Sunday
             | Monday
             | Tuesday
             | Wednesday
             | Thursday
             | Friday
             | Saturday
             deriving Show

isWeekend :: Weekday -> Bool
isWeekend Saturday = True
isWeekend Sunday   = True
isWeekend _        = False

nextDay :: Weekday -> Weekday
nextDay Sunday    = Monday
nextDay Monday    = Tuesday
nextDay Tuesday   = Wednesday
nextDay Wednesday = Thursday
nextDay Thursday  = Friday
nextDay Friday    = Saturday
nextDay Saturday  = Sunday

main :: IO ()
main = do
    print $ isWeekend Sunday    -- True
    print $ isWeekend Monday    -- False
    print $ isWeekend Saturday  -- True
    print $ nextDay Friday      -- Saturday
    print $ nextDay Saturday    -- Sunday

述語と量化 — 集合を条件で語る

外延表記は, 要素を書き並べる方法でした. しかし「1 以上 10 以下の偶数」のように, 要素を 条件 で指定したいことも多くあります. その基礎になるのが 述語 です.

要素 x について真偽が定まる主張を 述語(predicate) といいます. たとえば「x は偶数である」「x \leq 5 である」は, x が決まれば真偽の定まる述語です. 述語 p(x) は x が決まらなければ真偽が定まりませんが, 集合 X の要素すべて / いずれかについて述べると, 真偽の定まる 命題 になります. その作り方が次の 2 つです.

• 全称命題(universal proposition): ｢X の すべての 要素が p を満たす｣. 記号で \forall x \in X.\ p(x) と書きます (\forall は ｢すべての(for all)｣ を表す全称記号).
• 存在命題(existential proposition): ｢p を満たす要素が X に 少なくとも 1 つ存在する｣. 記号で \exists x \in X.\ p(x) と書きます (\exists は ｢存在する(there exists)｣ を表す存在記号).

たとえば ｢すべての非負実数は 0 以上である｣ は \forall x \in \mathbb{R}^+.\ x \geq 0 (全称命題), ｢平方して 2 になる実数が存在する｣ は \exists x \in \mathbb{R}.\ x^2 = 2 (存在命題) です.

この \forall / \exists を使うと, 言葉で述べてきた集合の性質を厳密に書けます. たとえば先に ｢集合には順序がなく \{x, y\} = \{y, x\}｣ と述べた 集合の等しさ は, ｢属する要素がまったく同じ｣こと, すなわち

A = B \quad\Longleftrightarrow\quad \forall x.\ (x \in A \iff x \in B)

と定義できます. 後の章(第8章 以降)では, 代数構造の 法則 (結合律や単位元の存在など) もこの全称・存在命題で正確に記述します. また本章の後半でも, 関係の性質 (反射律・対称律など) を \forall で書きます.

部分集合

集合には集合が属することも可能で, 集合 S が T に属するとき S \in T が成り立ちます. また, 集合 S の要素を幾つか取り出した集合 T を S の 部分集合 といい, T \subset S と表記します. いま導入した全称命題を使うと, これは ｢T のすべての要素が S にも属する｣こと, すなわち

T \subset S \quad\Longleftrightarrow\quad \forall x.\ (x \in T \implies x \in S)

と厳密に定義できます. この定義では, 空集合 \phi と S 自身も S の部分集合に含まれます.

S = \{x, y, z\} のとき, S の部分集合は

\{x\},\ \{y\},\ \{z\},\ \{x, y\},\ \{x, z\},\ \{y, z\},\ \{x, y, z\},\ \phi

となります.

この包含関係を ベン図 で見ると次のようになります. たとえば T = \{x, y\} は S = \{x, y, z\} の部分集合の 1 つです.

集合 X と述語 p が与えられると, ｢X の要素のうち p を満たすもの｣という部分集合がひとつ定まります. この部分集合を書き下すための記法が, 次節の 内包表記 です.

内包表記 — 述語で部分集合を切り出す

列挙型において見た 外延表記 に対して, 内包表記 とは, 集合を述語によって指定する方法です.

x の属する集合を X, 条件式 (述語) を p(x) とすると, 内包表記では

S = \{x \mid x \in X, p(x)\}

という記法で, ｢X の要素のうち p(x) を満たす要素のみからなる集合 S｣ — すなわち述語 p で切り出した X の部分集合 — を定義します.

例として, \mathbb{R}^+ を非負の実数としたとき, 5 以下の非負の実数は

\{x \mid x \in \mathbb{R}^+, x \leq 5\}

と書けます.

Haskell の代数的データ型では, 内包表記に基づくデータ型の定義そのものは提供されていません. しかし, 値のレベル では リスト内包表記 によって擬似的な集合計算が可能です. また 型のレベル で述語による絞り込みを実現するイディオムとして スマートコンストラクタ があります (本章後半の「スマートコンストラクタ (発展)」で扱います).

リスト内包表記による計算

リスト内包表記 は Haskell の標準構文で, 集合論の内包表記と非常に似た形でリストを構成できます. 集合論では

S = \{x \mid x \in X, p(x)\}

と書くところを, Haskell では

s = [ x | x <- xs, p x ]

と書きます. x <- xs が x \in X に対応する ジェネレータ, p x が述語 p(x) に対応する ガード です.

例として, 集合論における「1 以上 10 以下の整数のうち偶数のみ」

E = \{x \mid x \in \mathbb{Z}, 1 \leq x \leq 10, x \bmod 2 = 0\}

は, リスト内包表記では以下のように記述できます.

evens :: [Int]
evens = [ x | x <- [1..10], x `mod` 2 == 0 ]
-- evens == [2,4,6,8,10]

ジェネレータやガードは複数書くこともでき, 集合論における直積 (複数の変数の並行走査) や条件の連言 (AND) に自然に対応します.

-- {(x,y) | x ∈ [1..3], y ∈ [1..3], x /= y}
pairs :: [(Int,Int)]
pairs = [ (x,y) | x <- [1..3], y <- [1..3], x /= y ]
-- [(1,2),(1,3),(2,1),(2,3),(3,1),(3,2)]

ただし, リスト内包表記は 値のレベル での構成であり, 得られるのはあくまで [Int] などのリストです. 「型として偶数のみからなる新しいデータ型」を定義しているわけではない点に注意してください.

import qualified Data.Set as Set

a, b :: Set.Set Int
a = Set.fromList [1,2,3,4]
b = Set.fromList [3,4,5,6]

main :: IO ()
main = do
    print $ Set.union        a b  -- fromList [1,2,3,4,5,6]  (和集合)
    print $ Set.intersection a b  -- fromList [3,4]          (積集合)
    print $ Set.difference   a b  -- fromList [1,2]          (差集合)
    print $ Set.member       3 a  -- True                    (要素判定)

-- 実行例
main :: IO ()
main = do
    print $ divisors 12       -- [1,2,3,4,6,12]
    print $ divisors 13       -- [1,13]
    print $ pythagoreans 20   -- [(3,4,5),(5,12,13),(6,8,10),(8,15,17),(9,12,15),(12,16,20)]

-- 1. n の正の約数: 1 から n までの整数のうち n を割り切るもの
divisors :: Int -> [Int]
divisors n = [ x | x <- [1..n], n `mod` x == 0 ]

-- 2. ピタゴラス数: a <= b <= c <= n かつ a^2 + b^2 = c^2
pythagoreans :: Int -> [(Int, Int, Int)]
pythagoreans n =
    [ (a, b, c)
    | a <- [1..n]
    , b <- [a..n]
    , c <- [b..n]
    , a*a + b*b == c*c
    ]

main :: IO ()
main = do
    print $ divisors 12
    print $ divisors 13
    print $ pythagoreans 20

有限集合での ∀・∃ の機械検査

述語と量化の節で導入した \forall / \exists は, 集合が 有限 であれば Haskell で機械的に検査できます. 道具は 2 つの標準関数です.

• and :: [Bool] -> Bool — リストの要素が すべて True のとき True
• or :: [Bool] -> Bool — リストの要素の どれかが True のとき True

第6章の fold の言葉で言えば and = foldr (&&) True, or = foldr (||) False です. これをリスト内包表記と組み合わせると, 全称命題と存在命題の有限版がそのまま書けます.

\forall x \in X.\ p(x) \;\approx\; \texttt{and [ p x | x <- xs ]}, \qquad \exists x \in X.\ p(x) \;\approx\; \texttt{or [ p x | x <- xs ]}

この 2 つを関数として切り出しておきます (even は偶数判定の標準関数で, x mod 2 == 0 と同じです).

-- ∀x ∈ xs. p x の有限版
forallOn :: [a] -> (a -> Bool) -> Bool
forallOn xs p = and [ p x | x <- xs ]

-- ∃x ∈ xs. p x の有限版
existsOn :: [a] -> (a -> Bool) -> Bool
existsOn xs p = or [ p x | x <- xs ]

main :: IO ()
main = do
    print $ forallOn [2,4,6,8,10] even            -- True  (すべて偶数)
    print $ forallOn [1..10] even                 -- False (奇数が混ざる)
    print $ existsOn [1..10] (\x -> x * x == 25)  -- True  (5 がある)
    print $ existsOn [1..10] (\x -> x * x == 26)  -- False

標準ライブラリには同じ働きをする all / any という関数もあります (forallOn xs p = all p xs, existsOn xs p = any p xs).

本章の後半では, この forallOn / existsOn を使って 関係の法則 (反射律・対称律・推移律など) を全数検査します.

直積型

A \times B = \{(a, b) \mid a \in A, b \in B\} を A と B の 直積(Cartesian Product) といいます. 直積は A と B から要素を一つずつ選んで並べた組 (a, b) 全体からなる集合です. 日本語では 積集合(intersection) と字面が似ていますが異なる概念なので注意しましょう. 両者の違いを図で対比すると次のようになります (積集合の正式な定義は直和型の節で扱います).

事例として \mathrm{MyDogs} と整数の集合 \mathbb{Z} の直積を考えると,

\mathrm{MyDogs} \times \mathbb{Z} = \{(d, n) \mid d \in \mathrm{MyDogs}, n \in \mathbb{Z}\}

となり, 「犬種と整数(たとえば年齢)のペア」全体の集合を表します. たとえば (\mathrm{GoldenRetriever}, 3), (\mathrm{Beagle}, 7) \in \mathrm{MyDogs} \times \mathbb{Z} です.

Haskell では既に定義した MyDogs と Int の直積に相当する型を, 次のように定義できます. ここでは「犬種と年齢のペアを持つデータ型 DogAge」を定義します.

data DogAge = MkDogAge MyDogs Int
            deriving Show

記法の解説:

• 左辺の DogAge は 型構築子(type constructor), 右辺の MkDogAge は データ構築子(data constructor) です. 直和型と違い, ここでは構築子は一つしかありません(| が無い).
• データ構築子の後ろに 複数の型を空白区切りで並べる ことで, その構築子が包む値が直積になります. MkDogAge MyDogs Int は「MyDogs と Int を並べた組」を構成するコンストラクタです.
• 関数としての型は MkDogAge :: MyDogs -> Int -> DogAge となり, カリー化された2引数関数のように扱えます.

値の生成とパターンマッチは以下のようになります.

goldenAge :: DogAge
goldenAge = MkDogAge GoldenRetriever 3

breedOf :: DogAge -> MyDogs
breedOf (MkDogAge d _) = d

ageOf :: DogAge -> Int
ageOf (MkDogAge _ n) = n

main :: IO ()
main = do
    print $ breedOf goldenAge  -- GoldenRetriever
    print $ ageOf   goldenAge  -- 3

集合論的に解釈すると,

\mathrm{DogAge} = \mathrm{MyDogs} \times \mathrm{Int}

となります. MkDogAge は2つの集合の要素を一組にまとめる対応

\mathrm{MkDogAge} : \mathrm{MyDogs} \times \mathrm{Int} \to \mathrm{DogAge}, \quad (d, n) \mapsto \mathrm{MkDogAge}\,d\,n

に対応します.

数え上げ — 「代数的」の意味 (その1)

列挙型は要素を数えられます. 型 A の要素数 (集合の大きさ) を |A| と書くと, |\mathrm{MyDogs}| = 5, |\mathrm{Bool}| = 2 です. では直積の大きさはどうなるでしょうか. 組 (a, b) の作り方は「a の選び方 |A| 通り × b の選び方 |B| 通り」なので,

|A \times B| = |A| \cdot |B|

となります. 直積の大きさは掛け算 です. 実際に Haskell で確かめてみましょう. 全要素の列挙には, リスト内包表記のジェネレータ 2 本 (= 直積の走査) がそのまま使えます.

data Size = Small | Medium | Large deriving Show

allDogs :: [MyDogs]
allDogs = [GoldenRetriever, BlackRetriever, ShetlandSheepdog, StandardPoodle, Beagle]

allSizes :: [Size]
allSizes = [Small, Medium, Large]

-- MyDogs × Size の全要素
allPairs :: [(MyDogs, Size)]
allPairs = [ (d, s) | d <- allDogs, s <- allSizes ]

main :: IO ()
main = do
    print $ length allDogs   -- 5
    print $ length allSizes  -- 3
    print $ length allPairs  -- 15  (= 5 * 3)

パターンマッチによる更新と as パターン

直積型の値から 一部だけを変えた値 が欲しいことはよくあります. Haskell では値は不変 (再代入できない) なので, ここでの「更新」とは元の値を書き換えることではなく, 一部を変えた新しい値を作って返す ことを指します.

レコード構文を導入する前に, まず素朴な方法 — パターンマッチで全フィールドを取り出し, コンストラクタで組み立て直す — を見ておきましょう. DogAge の年齢を 1 増やす関数は次のように書けます.

growOlder :: DogAge -> DogAge
growOlder (MkDogAge b n) = MkDogAge b (n + 1)

変えたいのは年齢 n だけですが, 変えないフィールド b まで明示的に取り出して並べ直す 必要があります. フィールド数が増えるほど記述は長くなり, さらに MkDogAge b (n + 1) は フィールドの順序に依存する ため, 将来 data 定義のフィールドを並べ替えると意味が静かに壊れます. この「全部書き直す」「順序に縛られる」という弱点は, 次節の レコード更新構文 で解消されます.

as パターン. 値を分解して組み立て直すのではなく, 元の値全体をそのまま使いたい こともあります. たとえば「年齢が一定以上ならそれ以上歳を取らせず元の値をそのまま返し, そうでなければ 1 歳増やす」関数では,「分解した部品 n」と「元の値全体」の両方が必要です. このとき, パターン全体に名前を束縛する 名前@(パターン) という記法 (as パターン) が使えます.

growOlder' :: DogAge -> DogAge
growOlder' dog@(MkDogAge b n)
  | n >= 20   = dog                 -- 元の値 dog をそのまま返す
  | otherwise = MkDogAge b (n + 1)  -- 1 歳増やした新しい値

dog@(MkDogAge b n) は, 引数全体を dog に束縛しつつ, 同時に中身を MkDogAge b n に分解して各フィールドを b, n で取り出します. これにより dog (全体) と b, n (部品) を一つのパターンで同時に扱え, 最初の分岐のように 値をそのまま返す ことも, 2 番目の分岐のように 作り直す こともできます.

as パターンは「全体と部分の両方が要る」場面のための記法であり, 更新そのものの道具ではない 点に注意してください. 1 フィールドだけ変えて残りをコピーする更新は, 次節のレコード更新構文の方が簡潔です (値を分解せず, 変えたいフィールドだけ書けます).

レコード構文

直積型では レコード構文(record syntax) を用いて各フィールドに名前を付けることができます. 直積型ではコンストラクタが一つのため, レコード構文の恩恵(アクセサ関数の自動生成やフィールド名による値の生成)が特に活きます.

data DogAge = MkDogAge { breed :: MyDogs
                       , age   :: Int
                       }
            deriving Show

この定義により, 以下のアクセサ関数が 自動的に 定義されます.

• breed :: DogAge -> MyDogs
• age :: DogAge -> Int

これらの アクセサ関数(accessor function) は, レコード構文の定義から GHCが自動生成するトップレベル関数 で, レコード値からフィールドの値を取り出す役割を持ちます. たとえば breed は手書きすれば

breed :: DogAge -> MyDogs
breed (MkDogAge b _) = b

と書いたものと等価で, パターンマッチによる取り出しを関数として包んだものに過ぎません. レコード構文の利点は, このような取り出し関数を フィールドごとに自前で書く手間が省ける ことにあります.

アクセサ関数は他の関数と全く同様に 第一級の値(first-class value) として扱えるため, 高階関数に渡したり, 関数合成 (.) で他の関数と繋げたり, 部分適用したりできます. パターンマッチによる取り出しを関数の中に書く場合と比べ, 簡潔に「フィールドを取り出してから何かする」という処理を組み立てられるのが大きな利点です.

dogs :: [DogAge]
dogs = [ MkDogAge GoldenRetriever 3
       , MkDogAge Beagle           7
       , MkDogAge StandardPoodle   5
       ]

-- 高階関数に渡す: 全ての犬の犬種だけを取り出したリスト
allBreeds :: [MyDogs]
allBreeds = map breed dogs
-- [GoldenRetriever, Beagle, StandardPoodle]

-- 高階関数に渡す: 年齢が 5 歳以上の犬を絞り込む
matureDogs :: [DogAge]
matureDogs = filter ((>= 5) . age) dogs
-- [MkDogAge Beagle 7, MkDogAge StandardPoodle 5]

-- 関数合成: 「犬種を取り出して show する」を一つの関数として定義
showBreed :: DogAge -> String
showBreed = show . breed

filter ((>= 5) . age) dogs のように, アクセサ関数 age と比較 (>= 5) を (.) で合成すれば「年齢を取り出して 5 以上か判定する」という関数を一行で表現できます. もしレコード構文を使わずにパターンマッチで毎回書いていたら, この箇所は filter (\d -> case d of MkDogAge _ n -> n >= 5) dogs のように冗長になります.

なお, アクセサ関数名はモジュール内のトップレベルにそのまま展開されるため, 同じモジュールで別のレコード型に同名のフィールドを定義すると衝突します(回避には DuplicateRecordFields 言語拡張や, dogAge / personAge のような接頭辞付きの命名規約などが用いられます).

レコード構文によって自動生成されるアクセサ関数は, この射影に対応します. すなわち \mathrm{DogAge} = \mathrm{MyDogs} \times \mathrm{Int} と見なせば, breed は第1成分への射影 \pi_1, age は第2成分への射影 \pi_2 にあたり,

\mathrm{breed}((d, n) \in \mathrm{DogAge}) = d

\mathrm{age}((d, n) \in \mathrm{DogAge}) = n

と書けます. このように, 直積型のレコード構文は集合論における直積と射影の構造を, そのまま Haskell の構文として写したものになっています.

値の生成はフィールド名を明示する形でも, 従来の位置引数の形でも可能です.

goldenAge :: DogAge
goldenAge = MkDogAge { breed = GoldenRetriever, age = 3 }

-- もしくは位置引数で
goldenAge' :: DogAge
goldenAge' = MkDogAge GoldenRetriever 3

main :: IO ()
main = do
    print $ breed goldenAge  -- GoldenRetriever
    print $ age   goldenAge  -- 3

また, レコード構文では 一部のフィールドのみを更新した新しい値 を作る記法も利用できます. 先に見たとおり値は不変なので, ここでも「更新」とは元の値を変更するのではなく, 一部を書き換えた 新しい値を返す ことを意味します.

olderGolden :: DogAge
olderGolden = goldenAge { age = 10 }
-- MkDogAge { breed = GoldenRetriever, age = 10 }

先ほどパターンマッチで全フィールドを書き直していた growOlder も, レコード更新構文なら 変えたい age だけ を書けば済みます. breed は自動的にコピーされ, フィールドを並べ替えても壊れません.

-- 位置パターンで書き直していた growOlder が, これだけ簡潔になる
growOlder :: DogAge -> DogAge
growOlder d = d { age = age d + 1 }

直和型の場合と異なり, 直積型のレコードフィールドは単一のコンストラクタに属しているため アクセサは全域関数 であり, 実行時エラーの心配はありません.

data DogInfo = JustBreed { dogBreed :: MyDogs }
             | WithAge   { dogBreed :: MyDogs, dogAge :: Int }
             deriving Show

ghci> dogAge (JustBreed GoldenRetriever)
*** Exception: No match in record selector dogAge

-- 実行例
main :: IO ()
main = do
    let alice = Person { personName = "Alice", personAge = 30, personEmail = "alice@example.com" }
        bob   = Person { personName = "Bob"  , personAge = 25, personEmail = "bob@example.com"   }
    print $ birthday alice           -- Alice の年齢が 31 に
    print $ totalAge alice bob       -- 55

data Person = Person
    { personName  :: String
    , personAge   :: Int
    , personEmail :: String
    } deriving Show

-- レコード更新構文で年齢のみを更新した新しい値を返す
birthday :: Person -> Person
birthday p = p { personAge = personAge p + 1 }

-- アクセサ関数 personAge を利用して合計を計算
totalAge :: Person -> Person -> Int
totalAge p1 p2 = personAge p1 + personAge p2

main :: IO ()
main = do
    let alice = Person { personName = "Alice", personAge = 30, personEmail = "alice@example.com" }
        bob   = Person { personName = "Bob"  , personAge = 25, personEmail = "bob@example.com"   }
    print $ birthday alice      -- Person {personName = "Alice", personAge = 31, personEmail = "alice@example.com"}
    print $ totalAge alice bob  -- 55

直和型

集合 A, B の 和集合(union) を A \cup B, 積集合(intersection) を A \cap B と表し, それぞれ以下で定義されます.

A \cup B = \{x \mid x \in A \lor x \in B\}

A \cap B = \{x \mid x \in A \land x \in B\}

A \cap B = \phi のとき, A \cup B を A と B の 直和(Direct sum) といいます.

3 つの概念をベン図で並べると次のとおりです.

事例として A, B \subset \mathrm{MyDogs}, A = \{\mathrm{GoldenRetriever}, \mathrm{BlackRetriever}, \mathrm{ShetlandSheepdog}\}, B = \{\mathrm{BlackRetriever}, \mathrm{StandardPoodle}\} のとき, 和集合 A \cup B と積集合 A \cap B はそれぞれ

A \cup B = \{\mathrm{GoldenRetriever}, \mathrm{BlackRetriever}, \mathrm{ShetlandSheepdog}, \mathrm{StandardPoodle}\}

A \cap B = \{\mathrm{BlackRetriever}\}

となります. 和集合は「A または B のいずれかに属する要素」を集めた集合, 積集合は「A と B の両方に属する要素」のみを集めた集合です. このとき A \cap B = \{\mathrm{BlackRetriever}\} \neq \phi なので, A と B は直和にはなりません. 一方, A = \{\mathrm{GoldenRetriever}, \mathrm{ShetlandSheepdog}\}, B = \{\mathrm{BlackRetriever}, \mathrm{StandardPoodle}\} のように共通要素がない場合は A \cap B = \phi となり, A \cup B は A と B の直和となります.

Haskell では既に定義した Int と MyDogs の直和に相当する型を, 次のように定義できます. ここでは「整数または MyDogs のいずれかの値を持てるデータ型 IntOrDog」を定義します.

data IntOrDog = MkInt Int
              | MkDog MyDogs
              deriving Show

記法の解説:

• 左辺の IntOrDog は 型構築子(type constructor), 右辺の MkInt, MkDog は データ構築子(data constructor) と呼ばれます. どちらも大文字で始める必要があります.
• | は「または」を意味し, IntOrDog の値は MkInt <整数> または MkDog <犬> のいずれかの形をとる, という 直和 を宣言します.
• データ構築子の後ろに書かれた Int, MyDogs は包み込む値の型です. 具体的には MkInt :: Int -> IntOrDog, MkDog :: MyDogs -> IntOrDog という関数として扱えます.

値を作ったり, パターンマッチで取り出したりできます.

describe :: IntOrDog -> String
describe (MkInt n) = "整数 " ++ show n
describe (MkDog d) = "犬 "   ++ show d

main :: IO ()
main = do
    putStrLn $ describe (MkInt 42)               -- 整数 42
    putStrLn $ describe (MkDog GoldenRetriever)  -- 犬 GoldenRetriever

集合論的に解釈すると, MkInt と MkDog という互いに異なるタグでくるむことで Int と MyDogs が 互いに素 な形で一つの型に合流するため,

\mathrm{IntOrDog} = \mathrm{Int} \cup \mathrm{MyDogs} \quad (\mathrm{Int} \cap \mathrm{MyDogs} = \phi)

という 直和 になります. 一般に, 代数的データ型の | で分けたコンストラクタは必ずタグで区別されるため, Haskell の直和型は常に直和の構造を持ちます.

なお, データ構築子は任意個の引数を取ることができ, MkPair Int MyDogs のように複数の型を並べると, その部分は 直積 になります. つまり直和型の各コンストラクタは「いくつかの直積をタグ付きで合流させたもの」として解釈できます.

このように, 直和にすることで互いに異なる型の値を一つの型に集約でき, 型安全性を保ったまま「複数の型のいずれかをとる値」を表現できるようになります. 動的型付け言語におけるダックタイピングに似た柔軟さを, 型システムの保証を壊さずに実現する手段と考えることができます.

数え上げ — 「代数的」の意味 (その2)

直和の大きさも数えてみましょう. タグで区別されるため要素が重複することはなく, 選び方は「A から選ぶ |A| 通り, または B から選ぶ |B| 通り」なので,

|A + B| = |A| + |B|

となります (直和を A + B とも書きます). 直和の大きさは足し算 です.

data DogOrSize = ADog  MyDogs
               | ASize Size
               deriving Show

-- DogOrSize の全要素: タグ付きで合流させる
allDogOrSize :: [DogOrSize]
allDogOrSize = [ ADog d | d <- allDogs ] ++ [ ASize s | s <- allSizes ]

main :: IO ()
main = print $ length allDogOrSize   -- 8  (= 5 + 3)

さらに, 本章冒頭で見た Unit 型 () は要素がちょうど 1 つ (|()| = 1), Void は要素が 0 個 (|\mathrm{Void}| = 0) でした. これで型の世界に 0, 1, 足し算 (直和), 掛け算 (直積) が揃ったことになります. これが「代数的 データ型」という名前の由来です — 型は数のように「計算」できる対象なのです.

-- 実行例
main :: IO ()
main = do
    print $ area (Circle 1)            -- 3.141592653589793
    print $ area (Rectangle 3 4)       -- 12.0
    print $ area (Triangle 3 4 5)      -- 6.0

data Shape = Circle Double
           | Rectangle Double Double
           | Triangle Double Double Double
           deriving Show

area :: Shape -> Double
area (Circle r)       = pi * r * r
area (Rectangle w h)  = w * h
area (Triangle a b c) = sqrt (s * (s - a) * (s - b) * (s - c))
  where
    s = (a + b + c) / 2

main :: IO ()
main = do
    print $ area (Circle 1)       -- 3.141592653589793
    print $ area (Rectangle 3 4)  -- 12.0
    print $ area (Triangle 3 4 5) -- 6.0

再帰的データ型

ここまでのデータ型 (直積・直和) は, すでにある型を有限個組み合わせる ものでした. もう 1 つ強力な作り方があります. データ型が自分自身を使って定義される —— これを 再帰的データ型 (recursive data type) といいます. 有限の定義で, いくらでも大きくなりうるデータ (列や木など) を表せます.

代表例として 自然数 を作ってみます. 「自然数とは, 0 であるか, またはある自然数の 次の数 (successor) である」と定義できます. これをそのまま直和型にすると, 次のようになります.

data Nat = Zero | Succ Nat deriving (Show, Eq)

コンストラクタ Succ が引数に Nat 自身 を取っている点が再帰です. 値は Zero, Succ Zero, Succ (Succ Zero), … と続き, それぞれ 0, 1, 2, \dots を表します. たとえば 3 は Succ (Succ (Succ Zero)) です. (Succ を何段も重ねるのは煩雑ですが, 第8章で Nat に数値リテラルを使えるようにし, 3 :: Nat と書けるようにします.)

構成子は「型を生成する演算」

この Zero と Succ を, 数学の目で見直してみましょう.

• Zero は引数を取らず, それ自体が Nat の値を 1 つ作ります. 数学的には 0 項演算 — 引数を 0 個取る演算, すなわち 定数 です.
• Succ :: Nat -> Nat は Nat を 1 つ受け取って Nat を返します. 数学的には 1 項演算 です.

一般に, n 個の引数を取る構成子は n 項演算 とみなせます (「演算」という言葉の正式な定義は, 本章後半の「演算 — 台の上で閉じた関数」の節で与えます). 遡れば, 本章で書いてきた構成子はすべてこの意味の演算でした — GoldenRetriever は 0 項演算 (定数), MkInt :: Int -> IntOrDog は 1 項演算, MkDogAge :: MyDogs -> Int -> DogAge は 2 項演算です. つまり data 宣言とは, 「この型の値をどの演算で生成するか」の宣言 だったのです.

この見方をすると, Nat の定義が数学で自然数を定める ペアノの公理 (Peano axioms) とまったく同じ構成であることがはっきりします. ペアノの公理は, 自然数を「台となる集合 \mathbb{N} と, 定数 0 と, 1 項演算 S (後者関数 successor — 「次の数」を返す) の 組 (\mathbb{N},\ 0,\ S)」として特徴づけます. (Zero, Succ) は, この (0, S) にそのまま対応します.

ここで 1 つ, 取り違えやすい点に注意します. 演算が働く土台の集合 (台集合 といいます) は 型 Nat 全体 = 無限集合 であって, Zero はその中の 1 要素 にすぎません. Nat のすべての値は Zero という唯一の 素材 から Succ で生成されますが, 「素材が 1 個であること」と「集合が 1 点であること」は別物です. 前節の数え上げの言葉で言えば |\mathrm{Nat}| は無限 — 有限の規則 (0 項演算 1 つと 1 項演算 1 つ) だけで, 無限個の要素をもつ集合を記述できる のが再帰的データ型の力です.

「集合とその上の演算の 組」というこの見方は, 次章の主役になります (第8章では, 組にさらに 法則 を課したものとして代数構造を定義します).

どこにも循環はない — 集合を下から立ち上げる

ところで, Nat の定義には気になる点があります. 定義の右辺に, 定義しようとしている Nat 自身 が現れている — これは循環ではないのでしょうか.

集合論的に見ると, Nat は

• \text{Zero} \in \mathrm{Nat}
• n \in \mathrm{Nat} ならば \text{Succ}\ n \in \mathrm{Nat}

を満たす 最小の集合 です. このように「自分自身を使った規則で定まる集合」を 帰納的に定義された集合 といいます. そして, この「最小の集合」が循環なしに作れることは, 本章で揃えた道具 (空集合・和集合・内包表記・部分集合) だけで確かめられます.

上の 2 つの規則を, 「集合 X を受け取り, 構成子を 1 段だけ 適用して作れる値の集合を返す」対応 \Phi (生成作用素) として書き直します.

\Phi(X) \;=\; \{\texttt{Zero}\}\ \cup\ \{\,\texttt{Succ}\ n \mid n \in X\,\}

右半分は, まさに本章の内包表記です. \Phi を空集合から繰り返し適用すると,

\Phi(\emptyset) = \{\texttt{Zero}\},\qquad \Phi^2(\emptyset) = \{\texttt{Zero},\ \texttt{Succ Zero}\},\qquad \Phi^3(\emptyset) = \{\texttt{Zero},\ \texttt{Succ Zero},\ \texttt{Succ (Succ Zero)}\},\ \dots

と 1 段ごとに新しい値が 1 つずつ加わり, 集合が下から育っていきます.

\emptyset \;\subseteq\; \Phi(\emptyset) \;\subseteq\; \Phi^2(\emptyset) \;\subseteq\; \cdots, \qquad \mathrm{Nat} \;=\; \bigcup_{n \ge 0} \Phi^n(\emptyset)

どの値も 有限ステップ目で必ず現れます. 定義が使っているのは「出来上がった Nat 全体」ではなく「前の段までに作れた値」だけ — 見かけは自己言及でも, 実際は完全にボトムアップの構成であり, 循環はどこにもありません.

この立ち上がりは, Haskell でそのまま実行できます. 集合をリストで表せば, \Phi はリスト内包表記そのものです.

data Nat = Zero | Succ Nat deriving (Show, Eq)

-- 生成作用素 Φ: 構成子を 1 段だけ適用して作れる値の集合 (リスト表現)
step :: [Nat] -> [Nat]
step xs = Zero : [ Succ n | n <- xs ]

main :: IO ()
main = do
    print (step [])                         -- [Zero]                              = Φ(∅)
    print (step (step []))                  -- [Zero,Succ Zero]                    = Φ²(∅)
    print (step (step (step [])))           -- [Zero,Succ Zero,Succ (Succ Zero)]   = Φ³(∅)
    print (length (iterate step [] !! 10))  -- 10   (Φ^10(∅) は 10 個の値を持つ)

(iterate f x は [x, f x, f (f x), ...] という適用列を返す標準関数で, !! 10 で 10 段目を取り出しています.)

再帰的データ型は, 再帰関数で処理します. 第5章で学んだ関数の再帰を思い出してください. 関数の場合分けが型のコンストラクタ (Zero / Succ n) に一対一で対応し, Succ n の枝で自分自身を再帰呼び出しします.

data Nat = Zero | Succ Nat deriving (Show, Eq)

-- Nat を Int に変換する (構造をたどって 1 ずつ数える)
toInt :: Nat -> Int
toInt Zero     = 0
toInt (Succ n) = 1 + toInt n

-- 自然数の足し算 (m の上に Succ を n 個積み直す)
add :: Nat -> Nat -> Nat
add Zero     m = m
add (Succ n) m = Succ (add n m)

main :: IO ()
main = do
  let three = Succ (Succ (Succ Zero))
      two   = Succ (Succ Zero)
  print (toInt three)            -- 3
  print (toInt (add three two))  -- 5

toInt も add も, 基底ケース (Zero) と 再帰ケース (Succ n) に分けて書かれており, 関数の再帰構造が型の再帰構造をそのままなぞっています. これが再帰的データ型を扱うときの基本パターンです. 見方を変えると, toInt は 構成子の置き換え です — 値の中の Zero を 0 に, Succ を (+1) に置き換えると結果が得られます (add n m は Zero を m に置き換え, Succ はそのまま). この「構成子を別の演算で置き換える」という読み方は, 第8章の準同型 (構造を保つ写像) につながる伏線です.

実は, これまで使ってきた リストも再帰的データ型 です. 「リストとは, 空リスト [] であるか, または先頭要素 x と残りのリスト xs をつないだ x : xs である」という再帰的な構造を持ち, 概念的には [] | x : xs と定義されます. 構成子の言葉で言えば, [] が 0 項演算, (:) が 2 項演算です. 第5章以降で (x : xs) をパターンマッチして再帰処理してきたのは, まさにこの再帰型をたどる操作でした. リストや木を 任意の要素型 について扱えるようにする一般化 (型引数) と, それらに代数構造 (モノイド) を載せる話は 第9章 で扱います.

type

これまで新しいデータを作成するためには data を利用してきました. しかし, 新しい型を作るほどではないものの, 同じ表現型 (たとえば Double) に文脈上の意味を持つ名前を与えて, 可読性を高めたい 場合があります. 既存のデータ型に別名を与える最も簡単な方法が, type を用いて 型シノニム (type synonym) と呼ばれる別名を導入する方法です.

例えば,

data Rectangle = Rectangle Double Double
    deriving Show

mkRectangle :: Double -> Double -> Rectangle
mkRectangle b h = Rectangle b h

としたとき, 最初の引数と2つ目の引数のどちらが底辺で, どちらが高さなのかが判別できません.

data Rectangle = Rectangle {bottom :: Double
                           ,height :: Double}
    deriving Show

mkRectangle :: Double -> Double -> Rectangle
mkRectangle b h = Rectangle {bottom = b, height = h}

のようにレコード構文を用いることでフィールド名による区別は可能ですが, 型注釈側にも意味のある名前が現れる方が, さらに可読性と解釈可能性が上がります.

type 新しい型名 = 既存のデータ型

の形式で記述することで, 以下のように同じ Double に別名を付けることができます.

type Bottom = Double
type Height = Double

data Rectangle = Rectangle {bottom :: Bottom
                           ,height :: Height}
    deriving Show

mkRectangle :: Bottom -> Height -> Rectangle
mkRectangle b h = Rectangle {bottom = b, height = h}

これは集合論的には, 既知の集合 \mathbb{R} に対して別名 \text{Bottom}, \text{Height} を与えたもの に等しく, 集合としては \text{Bottom} = \text{Height} = \mathbb{R} で完全に同一です. つまり type は 新しい集合 (型) を構成しているわけではなく, 既存の型に別名 (alias) を導入しているだけ であり, 役割は 可読性のための注釈 に限られます.

newtype

type は既存の型に別名を付けるだけなので, 型検査上は元の型と完全に同じものとして扱われます. そのため, 前節の

type Bottom = Double
type Height = Double

では, Bottom と Height はどちらも Double の別名にすぎません. 型注釈を読む人間にとっては意味が分かりやすくなりますが, コンパイラは底辺と高さを別の型として区別しません.

型レベルで \text{Bottom} と \text{Height} を区別したい場合には, newtype を使います. newtype は既存の型を 1 つだけ包んで, 新しい独立した型を作るための構文です.

newtype 新しい型名 = コンストラクタ名 既存の型

例えば, 底辺と高さをそれぞれ独立した型として定義するには, 次のように書きます.

newtype Bottom = Bottom Double
newtype Height = Height Double

ここで左辺の Bottom, Height は 型構築子 です. 一方, 右辺の Bottom, Height は データ構築子 です. 名前は同じでも, 型の名前と値を作る関数の名前として別の名前空間に属しています.

データ構築子としての型は, それぞれ次のようになります.

Bottom :: Double -> Bottom
Height :: Double -> Height

つまり, Bottom 3.0 は Double の 3.0 を Bottom 型として包んだ値であり, Height 3.0 とは型が異なります.

この性質を使うと, 長方形の底辺と高さの取り違えを型検査で防げます.

newtype Bottom = Bottom Double deriving Show
newtype Height = Height Double deriving Show

data Rectangle = Rectangle Bottom Height
    deriving Show

mkRectangle :: Bottom -> Height -> Rectangle
mkRectangle b h = Rectangle b h

main :: IO ()
main = print (mkRectangle (Bottom 3.0) (Height 4.0))

このとき, mkRectangle は第一引数に Bottom, 第二引数に Height を要求します. そのため, 次のように底辺と高さを逆に渡そうとすると, コンパイルエラーになります.

-- mkRectangle (Height 4.0) (Bottom 3.0)

type Bottom = Double では Bottom も Height も実体は同じ Double なので, このような取り違えをコンパイラは検出できません. 一方, newtype では Bottom と Height は別々の型なので, 取り違えは型エラーになります.

newtype で包んだ値を計算に使うには, パターンマッチで中身を取り出します. 例えば, 長方形の面積を求める関数は次のように書けます.

newtype Bottom = Bottom Double deriving Show
newtype Height = Height Double deriving Show

data Rectangle = Rectangle Bottom Height
    deriving Show

area :: Rectangle -> Double
area (Rectangle (Bottom b) (Height h)) = b * h

Rectangle (Bottom b) (Height h) というパターンにより, Bottom の中の Double を b に, Height の中の Double を h に取り出しています. newtype で作った値は元の Double と同じように自動で計算に使えるわけではありません. 別の型として包んだので, 必要な場所で明示的に取り出す 必要があります.

集合論的に見ると, type は既存の集合に別名を付けているだけです. したがって,

\text{Bottom} = \text{Height} = \mathbb{R}

とみなせます. 一方, newtype は既存の集合と同じ要素数を持つ タグ付きのコピー を作っていると考えられます. Bottom も Height も中身は Double ですが, Haskell の型検査上は,

\text{Bottom} \neq \text{Height}

として扱われます. つまり, Double と Bottom は互いに変換可能なほどよく似ていますが, プログラム上では明示的に包む / 取り出す操作を通じて区別されます.

newtype Positive = Positive Int

badPositive :: Positive
badPositive = Positive (-1)

スマートコンストラクタ (発展)

内包表記の節で予告した, 型のレベル で「他のデータ型から述語で絞り込んだ新しいデータ型」を作る方法が, スマートコンストラクタ というイディオムです. 代数的データ型の data / newtype 宣言そのものには述語で絞り込む機能はないため, 前節の newtype とモジュールシステムを組み合わせて事実上の絞り込みを実現します. module など今後の学習内容を先取りしたかなり発展的な内容になるので, 対象は興味のある人のみとします.

たとえば, Int のうち「3の倍数」のみを要素とするデータ型 Mult3

\mathrm{Mult3} = \{n \mid n \in \mathrm{Int}, n \bmod 3 = 0\}

を作りたいとします. 以下のようにモジュールを定義します.

module Mult3
  ( Mult3        -- 型名は公開
  , mkMult3      -- スマートコンストラクタ
  , unMult3      -- 値の取り出し
  ) where

-- コンストラクタ Mult3 は公開しない (モジュール外から直接作れないようにする)
newtype Mult3 = Mult3 Int

-- 検査付きのコンストラクタ: 3 の倍数のときのみ Just を返す
mkMult3 :: Int -> Maybe Mult3
mkMult3 n
  | n `mod` 3 == 0 = Just (Mult3 n)
  | otherwise      = Nothing

-- 値の取り出し
unMult3 :: Mult3 -> Int
unMult3 (Mult3 n) = n

ポイントは, module 宣言の出力リストで コンストラクタ Mult3 をエクスポートしていない ことです. これにより, Mult3 型の値はモジュール外からは必ず mkMult3 を経由してしか作れず, かつ mkMult3 は 3 の倍数のときしか値を返しません. したがって Mult3 型の要素は必然的に \{n \in \mathrm{Int} \mid n \bmod 3 = 0\} という述語付きの集合に対応する, という保証が値の生成経路のレベルで得られます.

利用側は以下のようになります.

import Mult3

main :: IO ()
main = do
    print $ mkMult3 9   -- Just (Mult3 9)
    print $ mkMult3 10  -- Nothing
    -- Mult3 10         -- ← コンパイルエラー: コンストラクタが見えない

関係 — 直積の部分集合

ここまでは, 集合 (型) を 作る 道具 — 列挙, 述語による部分集合, 直積, 直和, 再帰 — を見てきました. 本章の残りでは, 集合の 間 のつながりを扱います.

「3 は 12 を割り切る」「x は y 以下である」「文字列 s と t は同じ長さである」— これらはどれも, 2 つのものの間で 真偽が定まる主張です. 述語と量化の節で見た述語 p(x) は変数が 1 つでしたが, これらは変数を 2 つ持つ述語 p(x, y) とみなせます. こうした「2 つのものの間の結びつき」を数学では 関係 (relation) と呼び, 集合論では次のように定義します.

つまり関係とは, 「結びついている対 (a, b) をすべて集めた集合」です. (a, b) \in R のとき, a と b は関係 R にあるといい, 中置記法 で a \mathrel{R} b とも書きます (たとえば 3 \leq 5 は, 対 (3, 5) が関係 \leq に属することの中置記法です).

部分集合は述語で切り出せるのでした (内包表記). 関係も同じで, 2 変数の述語 p(a, b) から

R = \{(a, b) \mid (a, b) \in A \times B,\ p(a, b)\}

と内包表記で定義できます. 本章前半の道具が, そのまま使えるわけです.

例として, 正の整数の間の 割り切る関係 を考えます. 「a が b を割り切る」(a \mid b と書きます) とは, b を a で割った余りが 0 であることです.

D = \{(a, b) \mid (a, b) \in \mathbb{Z}^+ \times \mathbb{Z}^+,\ b \bmod a = 0\}

(3, 12) \in D (3 は 12 を割り切る) ですが, (5, 12) \notin D です.

Haskell では, 有限の範囲であればこの関係をリスト内包表記でそのまま計算できます. また, 「対 (a, b) が関係にあるか」の判定は Bool を返す 2 引数関数 として書けます.

-- 判定関数: a は b を割り切るか
divides :: Int -> Int -> Bool
divides a b = b `mod` a == 0

-- 関係 D の {1..n} の範囲での全体像 (内包表記そのまま)
dividesPairs :: Int -> [(Int, Int)]
dividesPairs n = [ (a, b) | a <- [1..n], b <- [1..n], a `divides` b ]

main :: IO ()
main = do
    print $ 3 `divides` 12   -- True
    print $ 5 `divides` 12   -- False
    print $ dividesPairs 4   -- [(1,1),(1,2),(1,3),(1,4),(2,2),(2,4),(3,3),(4,4)]

ここで a `divides` b のようにバッククォートで囲むと 2 引数関数を中置で書けるのでした (第5章). 数学の中置記法 a \mid b と Haskell の a `divides` b がきれいに対応します.

対応関係を整理します. 集合としての関係 R \subseteq A \times B と, 判定関数 r :: a -> b -> Bool は,

(a, b) \in R \quad\Longleftrightarrow\quad \texttt{r a b} = \texttt{True}

によって行き来できます. 実は, これまで使ってきた ==, <=, < などの比較演算子は, すべてこの意味での「関係の判定関数」です. 関係を Bool への 演算 として本格的に扱い直すのは 第8章の仕事です.

なお, 変数を 3 つ以上持つ関係も同様に定義できます (n 項関係 = A_1 \times \dots \times A_n の部分集合) が, 本章では最もよく使う 2 項関係のみを扱います.

-- 実行例
main :: IO ()
main = do
    print $ coprime 8 15     -- True
    print $ coprime 6 9      -- False (gcd 6 9 == 3)
    print $ coprimePairs 4   -- [(1,1),(1,2),(1,3),(1,4),(2,1),(2,3),(3,1),(3,2),(3,4),(4,1),(4,3)]
    print $ and [ coprime b a | a <- [1..20], b <- [1..20], coprime a b ]  -- True (対称)

coprime :: Int -> Int -> Bool
coprime a b = gcd a b == 1

coprimePairs :: Int -> [(Int, Int)]
coprimePairs n = [ (a, b) | a <- [1..n], b <- [1..n], coprime a b ]

main :: IO ()
main = do
    print $ coprime 8 15
    print $ coprime 6 9
    print $ coprimePairs 4
    print $ and [ coprime b a | a <- [1..20], b <- [1..20], coprime a b ]

関数 — 特別な関係

関係を定義すると, 実は 関数も関係の一種 として捉え直せます.

関数 f : A \to B が与えられたとき, 「入力と出力の対」をすべて集めた集合

G_f = \{(x, f(x)) \mid x \in A\} \subseteq A \times B

を f の グラフ (graph) といいます. グラフは直積の部分集合なので, まさに関係です. 中学・高校で y = x^2 の「グラフ」を座標平面 (= \mathbb{R} \times \mathbb{R} の直積) に描いてきたのは, 文字通りこの意味のグラフ — 関係 \{(x, y) \mid y = x^2\} の図示 — でした.

Haskell でも, 有限の範囲なら関数のグラフをリスト内包表記で作れます.

square :: Int -> Int
square x = x * x

-- xs の範囲での f のグラフ {(x, f x) | x ∈ xs}
graphOn :: [a] -> (a -> b) -> [(a, b)]
graphOn xs f = [ (x, f x) | x <- xs ]

main :: IO ()
main = print $ graphOn [1..5] square   -- [(1,1),(2,4),(3,9),(4,16),(5,25)]

では逆に, どんな関係 G \subseteq A \times B も何かの関数のグラフになっているでしょうか. そうではありません. 関係が 関数のグラフ であるためには, 次の 2 条件が必要です.

• 全域性 (totality): どの入力にも出力がある. \forall x \in A.\ \exists y \in B.\ (x, y) \in G
• 右一意性 (right-uniqueness): 1 つの入力に対する出力は 1 通りしかない. \forall x \in A.\ \forall y, y' \in B.\ \big((x, y) \in G \land (x, y') \in G\big) \implies y = y'

この 2 条件を満たす関係は, ちょうど 1 つの関数 f : A \to B を定めます. すなわち, 関数とは全域かつ右一意な関係 のことです. ここでも \forall と \exists が定義の骨格を担っていることに注目してください.

この見方の効用の 1 つは, 「関数になりそこねた関係」— 部分関数 (partial function) — を正確に語れることです. 部分関数とは, 右一意だが 全域性を欠く 関係, つまり「出力が定義されない入力がある」対応のことです. 実は, 既にいくつも登場しています.

• head :: [a] -> a — 空リスト [] に対する出力がありません (第5章で見た実行時エラーの代表例).
• 直和型のレコードアクセサ — 「レコード構文」節の警告で見た dogAge は, WithAge の値にしか出力を持たず, JustBreed の値に適用すると No match in record selector になります.

Haskell の型 A -> B は, この全域性までは保証してくれません. head のような部分関数も型検査は通り, 定義されていない入力に出会ったときに 実行時エラー として破綻します. 対処の方向は 2 つあります. (1) 定義域を型で絞る — 「空でないリスト」のような型を作り, 危険な入力をそもそも渡せなくする (スマートコンストラクタはその道具の 1 つでした). (2) 出力を広げる — 「出力が無いかもしれない」ことを型で表す Maybe を使う (詳しくは 第9章で扱います).

なお, 第5章で学んだパターンマッチによる関数定義は, この見方では「グラフのどの部分に対 (x, f(x)) を置くか」を場合分けで指定する記法だと読めます. すべての入力パターンを尽くせば全域な関数になり, 尽くさなければ (head のように) 部分関数になります.

演算 — 台の上で閉じた関数

関数を正式に定義できたので, 本章でここまで非公式に使ってきた 演算 (operation) という言葉も, ここで整理しておきます. 再帰的データ型の節で構成子を「0 項演算」「1 項演算」と呼びました — その一般定義です.

ポイントは 2 つです.

• 演算は関数の特別な場合 であって, 別種の概念ではありません. 出発点が台 A の直積で, 行き先も同じ A — つまり 台の中で閉じている — という 形の制約 が付いた関数の呼び名です.
• 演算は アリティで種類分け されます. n = 2 が最も身近ですが, n = 1, n = 0 も演算です.

0 項演算が定数である理由. A^0 (0 個の直積) は空集合ではなく, 空タプル () だけを要素とする 1 点集合 です (直和型の数え上げで見た \lvert () \rvert = 1 の集合がこれです). したがって A^0 \to A という関数は, 「唯一の入力 () に対して A の要素を 1 つ返す」— すなわち A の要素を 1 つ指定すること と同じです. 「引数が無い」のではなく「情報を持たない引数が 1 つある」と読むのが正確で, これが「0 項演算 = 定数」の中身です.

演算でない関数. 行き先が台の 外 に出る関数は, その台の上の演算ではありません.

-- 2 項演算: 台 Int の中で閉じている
plus :: Int -> Int -> Int
plus x y = x + y

-- 1 項演算
neg :: Int -> Int
neg x = negate x

-- 0 項演算 = 定数
zero :: Int
zero = 0

-- 演算ではない関数: 台 [Int] から外 (Int) へ出ていく
len :: [Int] -> Int
len xs = length xs

main :: IO ()
main = do
    print (plus 3 4)     -- 7
    print (neg 5)        -- -5
    print zero           -- 0
    print (len [1,2,3])  -- 3

len (= length) はリストの世界から 出ていく ので, リストの上の演算ではありません — こうした「世界から世界へ渡る関数」は, 第8章で 準同型 (構造を保つ写像) として主役になります. また, 関係の判定関数 divides :: Int -> Int -> Bool も行き先が Bool なので Int の上の演算ではありません (ただし Bool をもう 1 つの台と認めて「Bool への 2 項演算」と読む立場もあり, 第8章でこの読み替えを使います).

この対比を, 3 枚つづきの図にしておきます. いちばん左の 図0 は, まだ何も載っていない 集合だけの世界 です — 点 (型 = 集合) が 1 つあるだけで, 射はありません. そこに演算を載せたのが 図1 — 演算の世界 です. 点はやはり 1 つ (台) のままで, 射 (矢印) はすべて台自身へ戻ってきます. 図の下に添えた成分の内訳 — 台 = \mathrm{Type}, 演算 = \bullet (2 項), e (0 項) — は, この世界を組として書き出したものです. いちばん右の 図2 が 関数の世界 です — 点 (型) は複数あり, 射は型から型へ自由に渡れます. こちらの内訳は \mathrm{Ob} = \{A, B, C\}, \mathrm{Mor} = \{f, g, g \circ f, \mathrm{id}, \dots\} — 点の集合と射の集合 の 2 本立てで, 成分の座席に「射の集まり」が入っています (この \mathrm{Ob} / \mathrm{Mor} という成分名は, 第9章の圏の定義でそのまま登場します). 演算とは, 図2 の射のうち「出発点と行き先が同じ点になるよう制約されたもの」だけを図1 の世界として取り出したものです (図1 のループはアリティを省いて描いています — \bullet の域は \mathrm{Type} \times \mathrm{Type}, e の域は \mathrm{Type}^0 ですが, 行き先が台に戻る点は同じです).

図1 から図2 へ移る操作 (図のいちばん右の矢印) を 俯瞰 と呼ぶことにします — 台を 1 つの集合に固定して眺めるのをやめ, 射 (関数) の集まりそのもの を視野に入れる, 見方の転換です. この図の系列はこのあとの章でそのまま再登場します. 図1 の世界に法則を課したものが代数 (第8章) であり, 俯瞰した図2 の世界 — 射の集まり — を新しい台とみなしたものが圏 (第9章) です.

カリー化との関係. 数学では 2 項演算を A \times A \to A (引数はペア 1 つ) と書きますが, Haskell では a -> a -> a (カリー化) が普通です. 第5章のカリー化で見たとおり, 両者は同じ情報の別表現です.

第8章では, この演算を台に載せ, \forall / \exists で書いた法則を課したもの — 構造 — を扱います. 本章の同値関係・順序関係 (関係) と, この節の演算が, そこで「組 + 法則」という 1 つの形に合流します.

同値関係 — 「同じ」の一般化

ここからは, 同じ集合 A の上の関係 R \subseteq A \times A に注目し, 特に重要な 2 種類 — 同値関係 と 順序関係 — を見ます. どちらも「関係が満たすべき法則」を \forall で書くことで定義されます. この「対象に法則を課す」という発想は次章の中心テーマになるので, ここで感触を掴んでおきましょう.

まず「等しい」の一般化から始めます. 集合 A 上の関係 R が次の 3 つの法則を満たすとき, R を 同値関係 (equivalence relation) といいます.

• 反射律 (reflexivity): \forall x \in A.\ x \mathrel{R} x — どの要素も自分自身と関係にある.
• 対称律 (symmetry): \forall x, y \in A.\ x \mathrel{R} y \implies y \mathrel{R} x — 向きを入れ替えても成り立つ.
• 推移律 (transitivity): \forall x, y, z \in A.\ (x \mathrel{R} y \land y \mathrel{R} z) \implies x \mathrel{R} z — 関係が連鎖する.

もっとも基本的な例は「等しい」(=) そのものです: x = x (反射), x = y \implies y = x (対称), x = y \land y = z \implies x = z (推移).

面白いのは, 「完全に等しい」わけではないのに同値関係になる例です. 整数の間の, 7 で割った余りが等しい という関係を考えます.

x \equiv y \pmod 7 \quad\Longleftrightarrow\quad x \bmod 7 = y \bmod 7

たとえば 0 \equiv 7 \equiv 14 \pmod 7 です. 「0 日目と 7 日目と 14 日目は同じ曜日」と読めば, これは「同じ曜日である」という関係にほかなりません. 日付として等しくなくても, 曜日という観点では「同じ」— 同値関係とは, このように 何かの観点で「同じ」とみなす ことの数学的な定式化です.

3 つの法則が本当に成り立つか, 有限範囲の全数検査で確かめてみましょう (forallOn は内包表記の節で定義したものです). 比較のために, 同値関係に ならない 例 — 「差が 1 以下」という関係 — も検査します.

-- ∀x ∈ xs. p x の有限版 (内包表記の節より)
forallOn :: [a] -> (a -> Bool) -> Bool
forallOn xs p = and [ p x | x <- xs ]

-- 7 で割った余りが等しい (「同じ曜日」)
congruent7 :: Int -> Int -> Bool
congruent7 x y = x `mod` 7 == y `mod` 7

-- 差が 1 以下 (「近い」)
nearBy :: Int -> Int -> Bool
nearBy x y = abs (x - y) <= 1

main :: IO ()
main = do
    -- congruent7 は 0..30 の範囲で 3 法則をすべて満たす
    print $ forallOn [0..30] (\x -> congruent7 x x)                 -- True (反射律)
    print $ and [ congruent7 y x | x <- [0..30], y <- [0..30]
                , congruent7 x y ]                                  -- True (対称律)
    print $ and [ congruent7 x z | x <- [0..30], y <- [0..30], z <- [0..30]
                , congruent7 x y, congruent7 y z ]                  -- True (推移律)
    -- nearBy は反射・対称だが, 推移律が破れる
    print $ nearBy 1 2 && nearBy 2 3   -- True  (1 と 2, 2 と 3 は近い)
    print $ nearBy 1 3                 -- False (しかし 1 と 3 は近くない)

対称律・推移律の検査に使った and [ 結論 | 変数の走査, 仮定 ] という形に注目してください. ガードを 仮定, 本体を 結論 とすることで, \forall x, y.\ (\text{仮定} \implies \text{結論}) という形の法則が, そのまま全数検査になります.

nearBy の例は, 「なんとなく等しさに似ている」だけでは同値関係にならないことを示しています. 「近い」は連鎖させると少しずつずれていくため, 推移律が破れるのです. 法則を \forall で明示して検査できる形にしておくことで, こうした直感の穴を機械的に発見できます.

同値関係は, 第8章で Eq 型クラス として Haskell に登場します. == を自分のデータ型に定義するとき, それが満たすべき法則が, まさにこの反射・対称・推移の 3 法則です.

-- 実行例
main :: IO ()
main = do
    print $ sameLength "ab" "xy"   -- True
    print $ sameLength "ab" "abc"  -- False
    -- 2. の検査 3 つがすべて True になること
    -- 3. の検査で破れる法則が見つかること

sameLength :: String -> String -> Bool
sameLength x y = length x == length y

evenProd :: Int -> Int -> Bool
evenProd x y = even (x * y)

words0 :: [String]
words0 = ["a", "ab", "abc", "xy", "z"]

main :: IO ()
main = do
    print $ sameLength "ab" "xy"    -- True
    print $ sameLength "ab" "abc"   -- False
    -- 2. sameLength は同値関係 (3 法則すべて True)
    print $ and [ sameLength x x | x <- words0 ]                        -- True (反射律)
    print $ and [ sameLength y x | x <- words0, y <- words0
                , sameLength x y ]                                      -- True (対称律)
    print $ and [ sameLength x z | x <- words0, y <- words0, z <- words0
                , sameLength x y, sameLength y z ]                      -- True (推移律)
    -- 3. evenProd は反射律が破れる (対称律は成り立つ)
    print $ and [ evenProd x x | x <- [1..10] ]   -- False
    print $ evenProd 1 1                          -- False (反例: x = 1. 1*1 = 1 は奇数)

順序関係 — 「並べる」の一般化

同値関係が「等しい」の一般化だったのに対し, 順序関係 は「大小で並べる」(\leq) の一般化です. 集合 A 上の関係 R が次の 3 つの法則を満たすとき, R を 半順序 (partial order) といいます.

• 反射律: \forall x \in A.\ x \mathrel{R} x
• 反対称律 (antisymmetry): \forall x, y \in A.\ (x \mathrel{R} y \land y \mathrel{R} x) \implies x = y — 両向きに成り立つのは同じ要素どうしだけ.
• 推移律: \forall x, y, z \in A.\ (x \mathrel{R} y \land y \mathrel{R} z) \implies x \mathrel{R} z

同値関係の定義と見比べてください. 反射律・推移律は共通で, 対称律が反対称律に置き換わった だけです. 対称的なら「同じとみなす」方向に, 反対称的なら「並べる」方向に関係の性格が決まる — どの法則を課すかが構造の性格を決める わけです.

半順序の例は, 数の \leq だけではありません.

• 部分集合関係 \subseteq: A \subseteq A (反射), A \subseteq B \land B \subseteq A \implies A = B (反対称 — これは述語と量化の節で見た集合の等しさの定義そのものです), A \subseteq B \land B \subseteq C \implies A \subseteq C (推移).
• 割り切る関係 \mid (正の整数上): a \mid a (反射), a \mid b \land b \mid a \implies a = b (反対称), a \mid b \land b \mid c \implies a \mid c (推移).

ここで, \leq と, \subseteq や \mid の間には大きな違いが 1 つあります. \leq では どの 2 要素も比較できます:

\forall x, y \in A.\ (x \mathrel{R} y \lor y \mathrel{R} x)

この性質を 全域比較可能性 (totality) といい, これも満たす半順序を 全順序 (total order) といいます. 一方 \mid では, たとえば 2 と 3 は どちらも他方を割り切りません — 比較不能な対が存在するため, 半順序ではあっても全順序ではありません.

割り切る関係で確かめてみましょう.

divides :: Int -> Int -> Bool
divides a b = b `mod` a == 0

main :: IO ()
main = do
    -- divides は {1..20} 上で半順序の 3 法則を満たす
    print $ and [ a `divides` a | a <- [1..20] ]                        -- True (反射律)
    print $ and [ a == b | a <- [1..20], b <- [1..20]
                , a `divides` b, b `divides` a ]                        -- True (反対称律)
    print $ and [ a `divides` c | a <- [1..20], b <- [1..20], c <- [1..20]
                , a `divides` b, b `divides` c ]                        -- True (推移律)
    -- しかし全順序ではない: 2 と 3 は比較不能
    print $ 2 `divides` 3 || 3 `divides` 2                              -- False

順序関係は, 第8章で Ord 型クラス として Haskell に登場します. compare や <= を自分のデータ型に定義するとき, それが満たすべき法則が全順序の法則です. 第5章で書いた挿入ソートのような並べ替えが常に意味を持つのは, 比較が全順序だからです — 比較不能な対があると「正しい並び順」が定まりません.

-- 実行例
main :: IO ()
main = do
    print $ [1,2] `subsetOf` [1,2,3]   -- True
    print $ [1,4] `subsetOf` [1,2,3]   -- False
    -- 2. 3. の検査がすべて True, 4. の反例が False になること

subsetOf :: [Int] -> [Int] -> Bool
subsetOf xs ys = and [ x `elem` ys | x <- xs ]

-- {1,2,3} の部分集合 8 個 (述語と量化の節で数えたとおり)
subsets :: [[Int]]
subsets = [[], [1], [2], [3], [1,2], [1,3], [2,3], [1,2,3]]

sameSet :: [Int] -> [Int] -> Bool
sameSet xs ys = subsetOf xs ys && subsetOf ys xs

main :: IO ()
main = do
    print $ [1,2] `subsetOf` [1,2,3]   -- True
    print $ [1,4] `subsetOf` [1,2,3]   -- False
    -- 2. 反射律と推移律
    print $ and [ s `subsetOf` s | s <- subsets ]                           -- True (反射律)
    print $ and [ a `subsetOf` c | a <- subsets, b <- subsets, c <- subsets
                , a `subsetOf` b, b `subsetOf` c ]                          -- True (推移律)
    -- 3. 反対称律 (sameSet の意味で)
    print $ and [ sameSet a b | a <- subsets, b <- subsets
                , a `subsetOf` b, b `subsetOf` a ]                          -- True (反対称律)
    -- 4. 全順序ではない: [1] と [2] は比較不能
    print $ [1] `subsetOf` [2] || [2] `subsetOf` [1]                        -- False

まとめ — 集合から構造へ

本章では, 型を集合とみなす見方を軸に, 集合を作る道具と, 集合の間・上の関係を整理しました.

後半で繰り返し現れた形に注目してください. 同値関係も順序関係も, 「関係という対象 に, \forall で書かれた 法則 を課したもの」として定義されました. そして法則は, 有限の範囲なら and とリスト内包表記で機械的に検査できました.

第8章では, この「対象に法則を課す」という組み立てを, 関係だけでなく 演算 に対して行います. 集合 (台) の上に演算を載せ, 結合律や単位元の存在といった法則を課したものが 代数構造 であり, Haskell では 型クラス がその受け皿になります. 本章の同値関係と全順序は, それぞれ Eq と Ord の法則として, 型クラスの世界にそのまま再登場します.