関数型言語と圏論

この記事は LLM と連携して作成しました

関数型言語を学んでいると、モナド・ファンクター・モノイドといった言葉に必ず出会う。これらの語源をたどると、多くは圏論という数学の一分野に行き着く。圏論そのものを知らなくても関数型言語は書けるが、用語の由来と満たすべき法則を知っておくと、ライブラリの API を「暗記」ではなく「導出」できるようになる。

この記事では、圏論の基本要素を体系的に整理したうえで、関数型言語の特徴が圏論のどの概念に対応するかをまとめる。モノイドとモナドについては、法則を実際の値で展開し、操作できる図も用意した。そして最後に、アルゴリズムを関数型的に考えると設計がどう変わるかを見ていく。

結論

圏とは、対象と射の集まりであり、射の合成が結合律と単位律を満たすものをいう
関数型言語の型はおおむね圏の対象、関数はおおむね圏の射に対応する。この対応のおかげで、関数合成の性質を圏論の法則として議論できる
ファンクターは圏から圏への構造を保つ写像で、プログラミングでは map を持つ型として現れる
モノイドは「結合的な二項演算」と「単位元」を持つ代数構造で、リストの連結や数値の加算はすべてモノイドの具体例。結合律があるからこそ fold を分割して並列化できる
モナドはファンクターに join（平坦化）を足したもので、bind（>>=、flatMap）は「fmap してから join する」ことの別名にすぎない
モナド則の 3 つは、bind による合成が結合律と単位律を満たすという主張であり、形はモノイド則とそっくりになる。実際「モナドは自己関手の圏におけるモノイド対象」と言い換えられる
IO モナドの結合律は「do ブロックの途中を関数に切り出しても、副作用の順番と結果は変わらない」という日常的な保証として効いてくる
自然変換は「対象ごとの工夫なしに、どの型でも同じ書き方で定義できる変換」であり、return と join はどちらも自然変換になっている
関数型でアルゴリズムを考えると、ループは畳み込みに、逐次処理は関数合成に、例外処理はモナドによる伝播に置き換わることが多い

前提

対象読者: Haskell や Scala、あるいは TypeScript の fp-ts のようなライブラリで、モナドやファンクターという語に出会ったことがある人
想定する知識: 集合と関数の基本的なイメージ。圏論や抽象代数の専門知識は前提にしない
ねらい: 圏論の公理を厳密に証明することではなく、関数型言語の設計判断を圏論の言葉で説明できるようになること
記事中のコードは Haskell の記法で書くが、>>= を flatMap に読み替えれば Scala や Java でもそのまま通じる

圏論の基礎

圏・対象・射

圏（category）は、次の要素からなる。

対象（object）の集まり。ここでは $A, B, C$ のように書く
射（morphism, arrow）の集まり。対象 $A$ から対象 $B$ への射を $f: A \to B$ と書く
射の合成（composition）。$f: A \to B$ と $g: B \to C$ があるとき、合成 $g \circ f: A \to C$ が定義される
各対象 $A$ に対する恒等射（identity morphism） $\mathrm{id}_A: A \to A$

対象と射だけを見ると集合と関数によく似ているが、圏論では対象の「中身」を問わない。対象は集合でもよいし、型でもよいし、状態機械の状態でもよい。重要なのは、射がどのように合成できるかという構造そのものだ。

flowchart LR
  A((A)) -- f --> B((B))
  B -- g --> C((C))
  A -- "g∘f" --> C

射の種類（モノ射・エピ射・同型射）

「射」というと、単射・全射・全単射を思い浮かべる人もいるだろう。しかし、これらは集合の圏（Set）における関数の性質であり、圏論一般でいう「射」とは抽象度が異なる。

圏論は対象の中身を見ない。射の合成だけから、単射・全射・全単射に相当する概念を定義できる。それぞれ次のように呼ぶ。

モノ射（monomorphism）: $f: A \to B$ は、任意の $g, h: X \to A$ に対して $f \circ g = f \circ h$ ならば $g = h$ が成り立つとき、モノ射と呼ばれる。Set では単射にあたる
エピ射（epimorphism）: $f: A \to B$ は、任意の $g, h: B \to X$ に対して $g \circ f = h \circ f$ ならば $g = h$ が成り立つとき、エピ射と呼ばれる。Set では全射にあたる
同型射（isomorphism）: $f: A \to B$ は、$g \circ f = \mathrm{id}_A$ かつ $f \circ g = \mathrm{id}_B$ を満たす $g: B \to A$ が存在するとき、同型射と呼ばれる。Set では全単射にあたる

モノ射・エピ射・同型射は、対象そのものを見ずに、射の合成と等号だけで定義されている。この記事で単に「射」と書く場合は、モノ射などの性質を限定しない。対象間の対応関係全般を指す言葉として使う。関手や自然変換の説明も、モノ射・エピ射・同型射に限定されない。

合成の法則: 結合律と単位律

圏であるためには、射の合成が次の 2 つの法則を満たす必要がある。

結合律（associativity）は、合成の順序を変えても結果が変わらないという法則だ。

$$h \circ (g \circ f) = (h \circ g) \circ f$$

単位律（identity law）は、恒等射を合成しても何も変わらないという法則だ。

$$\mathrm{id}_B \circ f = f = f \circ \mathrm{id}_A \quad (f: A \to B)$$

この 2 つだけを要求する点が圏論の抽象度を決めている。集合と関数の圏（Set）はもちろん、型と関数の圏、あるいは状態遷移の圏も、この 2 法則さえ満たせば「圏」として同じ道具立てで扱える。

なお、結合律は「括弧の付け替えを許す」法則であって、「順番の入れ替えを許す」法則ではない。順番の入れ替えを許すのは可換律という別の法則で、圏論も、次に出てくるモノイドも、可換律までは要求しない。関数合成や文字列連結が順番に依存することを思い出すと分かりやすい。

関手（functor）

関手は、ある圏 $\mathcal{C}$ から別の圏 $\mathcal{D}$ への「構造を保つ写像」だ。対象を対象に、射を射に対応させ、次の 2 つの法則を満たす必要がある。

$$F(\mathrm{id}_A) = \mathrm{id}_{F(A)}$$$$F(g \circ f) = F(g) \circ F(f)$$

つまり、関手は「合成する前に写しても、合成した後に写しても結果が同じ」という性質を持つ写像だ。この性質のおかげで、関手を通した先でも合成の振る舞いを信頼できる。

プログラミングでは、Maybe や [] のように「型を受け取って型を返す型構築子」であって、なおかつ map を持つものが関手にあたる。ここで写す先も型と関数の圏なので、正確にはある圏からその圏自身への関手、すなわち自己関手（endofunctor）になっている。この「自己」であることが、あとでモナドを組み立てるときに効いてくる。

自然変換（natural transformation）

自然変換は、2 つの関手 $F, G: \mathcal{C} \to \mathcal{D}$ の間の変換で、圏 $\mathcal{C}$ のどの対象 $A$ を選んでも整合する射 $\eta_A: F(A) \to G(A)$ の集まりをいう。任意の射 $f: A \to B$ について、次の図式が可換になることが要求される。

$$\eta_B \circ F(f) = G(f) \circ \eta_A$$

図で書くと四角形になり、「どちら回りでも同じ結果になる」ことを要求している。

flowchart LR
  FA["F(A)"] -- "F(f)" --> FB["F(B)"]
  FA -- "η_A" --> GA["G(A)"]
  GA -- "G(f)" --> GB["G(B)"]
  FB -- "η_B" --> GB

プログラミングに翻訳すると、$F$ と $G$ は Maybe や [] のような型構築子、$F(f)$ と $G(f)$ はそれぞれの fmap、$\eta$ は型構築子をまたぐ変換関数になる。つまり自然変換とは、次の式が成り立つ変換関数 eta のことだ。

1
2

-- どんな f を選んでも、この 2 つは等しくなる
fmap f . eta  ==  eta . fmap f

代表的な例を挙げる。

変換	型	内容
`maybeToList`	`Maybe a -> [a]`	`Just x` を `[x]`、`Nothing` を `[]` にする
`listToMaybe`	`[a] -> Maybe a`	先頭があれば `Just`、空なら `Nothing`
`reverse`	`[a] -> [a]`	リストを逆順にする（`[]` から `[]` への自然変換）
`concat`	`[[a]] -> [a]`	入れ子のリストを 1 段平坦化する

いずれも共通しているのは、中身の値を一切見ていないことだ。使っている情報は入れ物の形だけだ。中身の型を問わないため、どの型に対しても同じコードが動く。逆に、中身を覗く変換は自然変換にならない。

-- 自然変換にならない例: 中身の値 x を見て長さを決めている
unnatural :: Maybe Int -> [Int]
unnatural (Just x) = replicate x x
unnatural Nothing  = []

この unnatural に f = (+1) と Just 3 を入れると、先に fmap f してから変換すると [4, 4, 4, 4]、先に変換してから fmap f すると [4, 4, 4] になり、四角形が閉じない。次の図で実際に確かめられる。

この図は JavaScript で描画する。JavaScript を有効にすると、図を操作しながら確認できる。

Haskell で forall a. Maybe a -> [a] のように型変数のまま書けるということは、a の中身に触れられないということでもある。この「触れないから一様になる」という事情のおかげで、Haskell では型がこの形をした全域関数はおおむね自動的に自然変換になる。パラメトリシティ（parametricity）や自由定理（free theorem）と呼ばれる性質で、undefined や seq が絡む場合など例外はあるが、実務の感覚としては「多相のまま書けたら自然」と考えてよい。

なぜ「自然」と呼ぶのか

自然変換の名前は、「対象ごとに個別の工夫をせず、同じやり方で一様に定義できる」という意味を持つ。歴史的には、Eilenberg と Mac Lane が 1945 年の論文でこの用語を導入した。基底に頼らず決まる対応を、この言葉で表した。

たとえば、ベクトル空間 $V$ とその双対空間 $V^*$、二重双対空間 $V^{**}$ を考える。

$$V \to V^{**}, \quad v \mapsto (\phi \mapsto \phi(v))$$

V から V^* への同型写像は存在するものの、基底を選ぶ必要がある。一方、V から V^{**} への写像は基底を選ばずに定義でき、線形写像同士でも図式が可換になる。基底を選ばずに定義できることが、自然変換という名前の由来だ。

プログラミングでいう「基底を選ぶ」は「中身の型を Int に決め打ちする」に近い。先ほどの unnatural が Int にしか書けなかったのは、まさに基底を選んでしまったからだ。

関数型言語と圏論の関係

型と関数の圏

関数型言語の型システムは、おおむね次のように圏論の言葉へ翻訳できる。

圏論の概念	プログラミングでの対応
対象	型（`Int`, `String`, `Maybe a` など）
射	関数（`f :: A -> B`）
合成	関数合成（`g . f`、パイプライン）
恒等射	恒等関数（`id`）
関手	`map` を持つ型（`Functor`）
自然変換	型をまたぐ一様な変換関数

Haskell では、この「型を対象、関数を射とする圏」を Hask と呼ぶことがある。ここで重要なのは、関数合成の結合律・単位律の成立が、Haskell の .（合成演算子）や id の設計そのものに直接反映されている点だ。

純粋関数と参照透過性

圏論の射が満たすべき性質を関数として実装するには、次の性質が欠かせない。

純粋関数（pure function）: 同じ入力には常に同じ出力を返し、副作用を持たない
参照透過性（referential transparency）: 式をその評価結果に置き換えても、プログラム全体の意味が変わらない

副作用のある関数を圏の射として扱おうとすると、実行順序や外部状態によって合成の結果が変わってしまい、結合律や単位律が成り立たなくなる。関数型言語が純粋関数を重視するのは、単なる好みではなく、関数合成を数学的に信頼できる操作にするための前提条件だといえる。

モノイド（monoid）

定義

モノイドは、次の要素からなる代数構造だ。

集合 $M$
二項演算（binary operation） $\oplus: M \times M \to M$
単位元（identity element） $e \in M$

満たすべき法則は次の 2 つだ。

$$(a \oplus b) \oplus c = a \oplus (b \oplus c) \quad \text{(結合律)}$$$$e \oplus a = a = a \oplus e \quad \text{(単位律)}$$

これは、対象が 1 つだけの圏として捉えることもできる。射の合成が二項演算に、恒等射が単位元に対応する。逆にいえば、モノイドは「圏の法則を、対象を 1 つに潰した状態で眺めたもの」だといえる。あとで見るモナド則が圏の法則と同じ形になるのも、根はここにある。

具体例で法則を確かめる

プログラミングでは、モノイドはいたるところに現れる。

型	演算	単位元
数値の加算	`+`	`0`
数値の乗算	`*`	`1`
リスト	`++`（連結）	`[]`
文字列	連結	`""`
論理和	`\|\|`	`False`
最大値	`max`	型の最小値

法則が成り立つかどうかは、抽象的に眺めるより実際の値を入れたほうが早い。加算を例にすると次のようになる。

結合律: (3 + 5) + 8 = 8 + 8 = 16
        3 + (5 + 8) = 3 + 13 = 16   → 一致

単位律: 0 + 3 = 3
        3 + 0 = 3                   → どちらも a と一致

一方、「2 つを 1 つにまとめる関数」でありながらモノイドにならない演算もある。減算と平均が分かりやすい。

減算の結合律: (3 - 5) - 8 = -10
              3 - (5 - 8) = 6       → 一致しない
減算の単位律: 3 - 0 = 3             → 右側は成り立つ
              0 - 3 = -3            → 左側は成り立たない

平均の結合律: avg(avg(3, 5), 8) = avg(4, 8)   = 6
              avg(3, avg(5, 8)) = avg(3, 6.5) = 4.75  → 一致しない
平均の単位元: そもそも存在しない

結合律と単位律をその場の値で確かめられる図を用意した。同じ 4 つの値を「左から順に畳んだ木」と「半分ずつ畳んだ木」が 1 ラウンドずつ同時に埋まっていくので、並列のほうが 1 ラウンド早く終わる様子と、結合律が壊れたときに何が起きるかを続けて見られる。

この図は JavaScript で描画する。JavaScript を有効にすると、図を操作しながら確認できる。

結合律が並列化を許す

モノイドの利点は、要素の並べ方を問わず並列に集約できることだ。結合律が保証されているため、fold の計算順序を分割・並列化しても結果が変わらない。図と同じ内容を Mermaid で書くと、まず素直な逐次の畳み込みはこうなる。

flowchart TD
  L3["((a⊕b)⊕c)⊕d"] --> L2["(a⊕b)⊕c"]
  L3 --> Ld["d"]
  L2 --> L1["a⊕b"]
  L2 --> Lc["c"]
  L1 --> La["a"]
  L1 --> Lb["b"]

対して、半分ずつ畳めば木の深さは半分になり、左右を別スレッドや別ノードに割り当てられる。

flowchart TD
  R2["(a⊕b)⊕(c⊕d)"] --> R0["a⊕b"]
  R2 --> R1["c⊕d"]
  R0 --> Ra["a"]
  R0 --> Rb["b"]
  R1 --> Rc["c"]
  R1 --> Rd["d"]

この 2 つの木が同じ値になることを保証しているのが結合律だ。ログの集計やイベントの集約処理を MapReduce のような形で分散させられるのは、集約関数がモノイドだからだといえる。単位元は、分割した結果が空だったときに返す値として効いてくる。

Haskell では次のように定義できる。

class Semigroup m where
  (<>) :: m -> m -> m        -- 結合律だけを要求する

class Semigroup m => Monoid m where
  mempty :: m                -- 単位元を足すとモノイドになる

instance Semigroup [a] where
  (<>) = (++)

instance Monoid [a] where
  mempty = []

結合律だけを満たす構造を半群（semigroup）と呼び、そこに単位元を足したものがモノイドになる。並列化に必要なのは結合律だけなので、半群でも分割はできる。単位元が要るのは「空の入力に何を返すか」を決めたいときだ。

モナド（monad）

「文脈付きの値」を繋ぐ

モナドの話は、Maybe Int を「失敗するかもしれない Int」、[Int] を「候補が複数ある Int」、IO Int を「実行すると Int を返す手続き」と読むところから始まる。いずれも「素の値」ではなく「何らかの文脈がくっついた値」だ。

このとき困るのは、文脈付きの値を返す関数どうしを繋ぐ場面だ。次の 2 つを順に適用したい。

half :: Int -> Maybe Int
half n = if even n then Just (n `div` 2) else Nothing

recip100 :: Int -> Maybe Int
recip100 0 = Nothing
recip100 n = Just (100 `div` n)

half の戻り値は Maybe Int で、recip100 の引数は Int だ。型が合わないので recip100 . half とは書けない。

なぜ `map` だけでは足りないのか

Maybe は関手なので fmap は使える。しかし fmap recip100 を Maybe Int に適用すると、戻り値は Maybe (Maybe Int) になる。

`1`	`fmap half (Just 40) -- Just (Just 20) :: Maybe (Maybe Int)`

もう一段進めたければ、recip100 を fmap でもう一枚持ち上げる必要がある。

1
2

fmap (fmap recip100) (Just (Just 20))
-- Just (Just (Just 5))  :: Maybe (Maybe (Maybe Int))

段が増えるたびに fmap を重ね、型は Maybe を 1 枚ずつ着込んでいく。これでは実用にならない。必要なのは、増えた Maybe を毎回 1 枚はがす操作だ。それが join（flatten）で、join を持つ関手がモナドになる。

1
2
3

join :: Maybe (Maybe a) -> Maybe a
join (Just m) = m
join Nothing  = Nothing

上下 2 段で「fmap だけで繋いだ場合」と「bind で繋いだ場合」を比べられる図を用意した。1 段ずつ同時に進むので、上段だけ型が 1 枚ずつ深くなる様子が見える。入力を変えれば、どの段で失敗しても下段の型は動かないと分かる。

この図は JavaScript で描画する。JavaScript を有効にすると、図を操作しながら確認できる。

`bind`、`flatMap`、`join` の関係

bind（>>=）は、この「fmap してから join する」を 1 つの操作としてまとめたものにすぎない。

$$m \mathbin{>\!\!>\!\!=} f = \mathrm{join}\,(\mathrm{fmap}\ f\ m)$$

逆に join は bind から作れる（join m = m >>= id）ので、両者はどちらを基本にしてもよい。図にすると、記事の最初に出てきた合成の三角形と同じ形をしている。

flowchart LR
  M["m :: M a"] -- "fmap f" --> MM["M (M b)"]
  MM -- "join" --> R["M b"]
  M -- "m >>= f" --> R

そして flatMap は bind の別名だ。名前が言語ごとに違うだけで、やっていることは同じ「map してから 1 段潰す」になる。

言語	名前	シグネチャの形
Haskell	`>>=`	`m a -> (a -> m b) -> m b`
Scala	`flatMap`	`M[A] => (A => M[B]) => M[B]`
Java	`Optional.flatMap`, `Stream.flatMap`	`Optional<A> -> Function<A, Optional<B>> -> Optional<B>`
JavaScript	`Array.prototype.flatMap`	`A[] -> (A => B[]) => B[]`
Rust	`Option::and_then`, `Result::and_then`	`Option<A> -> (A -> Option<B>) -> Option<B>`

flatMap という名前は「map の結果を flat（平坦化）する」という手続きをそのまま表している。flatten が join にあたるので、flatMap = map + flatten = fmap + join = bind という対応になる。JavaScript の [1,2].flatMap(x => [x, x*10]) が [1, 10, 2, 20] を返すのは、map の結果 [[1,10],[2,20]] を concat で 1 段潰しているからだ。

モナドの構成要素と法則

以上をまとめると、モナドは次の 3 つの要素からなる。

型構築子（type constructor） $M$（Maybe, Either e, [], IO など）
return（pure）: $a \to M\,a$
bind（>>=）: $M\,a \to (a \to M\,b) \to M\,b$

満たすべき法則は次の 3 つで、モノイドの法則と同じ形をしている。

$$\mathrm{return}(a) \mathbin{>\!\!>\!\!=} f = f(a) \quad \text{(左単位律)}$$$$m \mathbin{>\!\!>\!\!=} \mathrm{return} = m \quad \text{(右単位律)}$$$$(m \mathbin{>\!\!>\!\!=} f) \mathbin{>\!\!>\!\!=} g = m \mathbin{>\!\!>\!\!=} (\lambda x \to f(x) \mathbin{>\!\!>\!\!=} g) \quad \text{(結合律)}$$

なぜモノイド則と同じ形になるのか。Kleisli 射（$a \to M\,b$ という形の関数）を射だと思うと、bind はその合成になり、return はその恒等射になるからだ。実際、Kleisli 合成を次のように定義できる。

1
2

(>=>) :: Monad m => (a -> m b) -> (b -> m c) -> (a -> m c)
f >=> g = \x -> f x >>= g

この >=> を合成、return を恒等射と見ると、モナド則の 3 つはそのまま圏の法則になる。

1
2
3

return >=> f  ==  f          -- 左単位律
f >=> return  ==  f          -- 右単位律
(f >=> g) >=> h  ==  f >=> (g >=> h)   -- 結合律

この圏を Kleisli 圏と呼ぶ。モナド則がモノイド則と同じ見た目をしているのは偶然ではなく、モナドが「Kleisli 圏における恒等射と合成が満たすべき、圏の法則そのもの」だからだ。

Maybe モナドで法則を展開する

抽象的な式のままでは腑に落ちにくいので、先ほどの half と recip100 を使って実際に展開する。

まず左単位律を確かめる。return 40 は Just 40 なので、次のようになる。

return 40 >>= half
  = Just 40 >>= half
  = half 40                -- Just x >>= f は f x に潰れる
  = Just 20
右辺 half 40 = Just 20     → 一致

次に右単位律を確かめる。

Just 20 >>= return
  = return 20
  = Just 20
右辺 m = Just 20           → 一致

最後に結合律を、成功する経路と失敗する経路の両方で確かめる。

成功する経路（m = Just 40）
  (Just 40 >>= half) >>= recip100
    = Just 20 >>= recip100 = Just 5
  Just 40 >>= (\x -> half x >>= recip100)
    = half 40 >>= recip100 = Just 20 >>= recip100 = Just 5   → 一致

失敗する経路（m = Just 7、half が奇数で失敗する）
  (Just 7 >>= half) >>= recip100
    = Nothing >>= recip100 = Nothing
  Just 7 >>= (\x -> half x >>= recip100)
    = half 7 >>= recip100 = Nothing >>= recip100 = Nothing   → 一致

Maybe にとって、この 3 法則が言っているのは次のことだ。

左単位律: Just に包んですぐ剥がすのは、何もしないのと同じ
右単位律: パイプラインの末尾に return を足しても、結果は変わらない
結合律: 短絡の判定をどこでまとめても、止まる位置は変わらない

実務的には、結合律が「途中の 2 ステップをヘルパー関数に切り出してよい」という保証になっている。half と recip100 をまとめた halfThenRecip = half >=> recip100 を作って m >>= halfThenRecip と書いても、元のコードと完全に同じ振る舞いをする。

IO モナドでの法則

IO は「副作用があるから法則が怪しいのでは」と思われやすいが、そうではない。ポイントは IO a の読み方にある。

IO a は「実行すると a を返す手続きの記述」であって、実行そのものではない。したがって、2 つの IO a が等しいとは「実行したときの副作用の並びと結果が同じ」という意味になる。この基準で 3 法則を確かめればよい。

step :: String -> Int -> IO Int
step tag v = do
  putStr tag
  pure v

m :: IO Int
m = step "A" 1

f, g :: Int -> IO Int
f x = step "B" (x + 1)
g x = step "C" (x * 10)

この m, f, g で 3 法則を展開すると次のようになる。

左単位律: pure 1 >>= f   → 出力 "B"、結果 2
          f 1            → 出力 "B"、結果 2      → 一致
右単位律: m >>= pure     → 出力 "A"、結果 1
          m              → 出力 "A"、結果 1      → 一致
結合律:   (m >>= f) >>= g                → 出力 "ABC"、結果 20
          m >>= (\x -> f x >>= g)        → 出力 "ABC"、結果 20   → 一致

IO にとって、それぞれの法則は次の意味を持つ。

左単位律: pure は副作用をまったく起こさない。だから x <- pure v は let x = v と同じ
右単位律: 手続きの末尾に pure を足しても、副作用と結果は増えない
結合律: 手続きの区切り方を変えても、副作用の順番と結果は変わらない

3 つ目の結合律は、do 記法のリファクタリングをするたびに使っている。do 記法は >>= の糖衣構文で、do { x <- m; rest } は m >>= \x -> do { rest } に展開される。したがって次の書き換えは、結合律そのものになる。

-- 切り出す前
main :: IO ()
main = do
  cfg  <- loadConfig "app.yaml"
  conn <- connect cfg
  rows <- query conn "select ..."
  print rows

-- 先頭 2 行を関数に切り出した後
setup :: IO Connection
setup = do
  cfg <- loadConfig "app.yaml"
  connect cfg

main :: IO ()
main = do
  conn <- setup
  rows <- query conn "select ..."
  print rows

「途中の数行を関数に切り出しても、ログの出る順番も DB に投げるクエリの順番も変わらない」という当たり前に見える性質は、結合律が成り立っているからこそ保証される。逆にいえば、結合律が壊れた bind を自作してしまうと、この当たり前が崩れる。

IO の flatMap が何をしているかも、この見方から素直に読める。readFile "a.txt" >>= writeFile "b.txt" は、「ファイルを読む手続き」と「読んだ内容を書く手続き」を 1 本の手続きに繋いだ記述を作っているだけで、この式を書いた時点ではまだ何も起きていない。map（fmap）との違いも同じで、fmap に「IO を返す関数」を渡すと IO (IO a) という「手続きを返す手続き」ができてしまう。join はそれを「外側を実行し、出てきた手続きも続けて実行する 1 本の手続き」へと潰す操作だ。

そのほかのモナドでの法則

主要なモナドについて、return と bind が何をしていて、法則が何を主張しているのかをまとめる。

モナド	`return`	`bind` の意味	結合律が言っていること	単位律が言っていること
`Maybe`	`Just x`	失敗したら以降を短絡	短絡の判定をどこでまとめても止まる位置は同じ	`Just` に包んで即剥がすのは何もしないのと同じ
`Either e`	`Right x`	最初のエラーを保持して短絡	同上。保持されるエラーも同じ	`Right` に包んで即剥がすのは何もしないのと同じ
`[]`	`[x]`	`concatMap`。全組み合わせを展開	入れ子のリストをどこから連結しても同じ	1 要素リストは連結の単位元と同じ働きをする
`Writer w`	`(x, mempty)`	値を渡してログを `<>` で連結	ログのモノイドの結合律そのもの	`mempty` がログの単位元
`State s`	`\s -> (x, s)`	状態を次の計算へ受け渡す	状態の受け渡し順が同じなら区切り方は自由	`return` は状態に触らない
`IO`	`pure x`	手続きを 1 本に連結	`do` ブロックの切り出しが安全	`pure` は副作用ゼロ

この表で目を引くのは、[] と Writer の行だ。どちらも結合律の根拠が「モノイドの結合律」になっている。

リストモナドの join は concat、つまり foldr (++) [] であり、リスト連結モノイドの畳み込みそのものだ。平坦化がモノイドの畳み込みでできているので、モナドの結合律はモノイドの結合律から出てくる。

Writer はもっと直接的で、定義に Monoid 制約が現れる。

newtype Writer w a = Writer (a, w)

instance Monoid w => Monad (Writer w) where
  return x                = Writer (x, mempty)
  Writer (a, w) >>= f     = let Writer (b, w') = f a
                            in  Writer (b, w <> w')

return はログを mempty（モノイドの単位元）にし、bind はログを <>（モノイドの演算）で繋ぐ。だからモナド則の証明は、そのままログのモノイド則の証明になる。

左単位律 ← mempty <> w = w
右単位律 ← w <> mempty = w
結合律 ← (w1 <> w2) <> w3 = w1 <> (w2 <> w3)

「モノイドが分かった上で bind が組み合わさるとモナドになる」という話が、いちばん見えやすい形で現れているのが Writer だといえる。

ここまでの内容は、モナドを選ぶと 3 法則の左辺と右辺を同じ m, f, g で実際に評価して並べる図で確認できる。IO は「実行すると（副作用の列, 値）を返す関数」としてモデル化してある。

この図は JavaScript で描画する。JavaScript を有効にすると、図を操作しながら確認できる。

法則が破れるとき

型が合っていても法則が成り立つとは限らない。図に入れてある「手数カウンタ」は、bind するたびに手数を 1 足す実装だ。

newtype Counted a = Counted (a, Int)   -- (値, bind した回数)

-- return はコストゼロ、bind は 1 手ぶん加算する
returnC x                = Counted (x, 0)
Counted (a, n) `bindC` f = let Counted (b, m) = f a in Counted (b, n + m + 1)

型は完全に合っていて map と flatMap のどちらも書けるが、m >>= return は m より手数が 1 多いので右単位律が壊れる。左単位律も同様に壊れる。結合律だけは、どちらの括弧の付け方でも bind が 2 回になるので偶然成り立つ。

実在の例では、JavaScript の Promise がよく引き合いに出される。then は flatMap のように見えるが、Promise.resolve が thenable を再帰的に平坦化してしまうため、Promise<Promise<T>> という値を作れない。そのため a 自身が Promise の場合、Promise.resolve(a).then(f) は f に a そのものではなく a の解決値を渡してしまい、f(a) と食い違う。左単位律が成り立たないので、厳密にはモナドとはいえないと説明されることが多い。実用上ほとんど困らないが、「flatMap らしき API があること」と「モナド則を満たすこと」は別だと覚えておくとよい。

モノイドとモナドはどうつながるのか

ここまで「モナド則はモノイド則と同じ形」と繰り返してきたが、これは比喩ではない。join と return を自然変換として書き直すと、対応が正確に一致する。

まず、モナドのもう 1 つの定義を挙げる。モナドとは、自己関手 $T$ と 2 つの自然変換の組 $(T, \eta, \mu)$ であって、

$$\eta: \mathrm{Id} \Rightarrow T \quad (\text{return}), \qquad \mu: T \circ T \Rightarrow T \quad (\text{join})$$

次の 2 つの図式が可換になるものをいう。

$$\mu \circ T\mu = \mu \circ \mu T \quad \text{(結合律)}$$$$\mu \circ T\eta = \mathrm{id}_T = \mu \circ \eta T \quad \text{(単位律)}$$

結合律のほうを図にすると、$T$ を 3 段重ねた状態からどちらの順で潰しても同じ、という主張になる。

flowchart LR
  T3["T∘T∘T"] -- "μT（外側から潰す）" --> T2a["T∘T"]
  T3 -- "Tμ（内側から潰す）" --> T2b["T∘T"]
  T2a -- "μ" --> T["T"]
  T2b -- "μ" --> T

Haskell で書けば、次の 3 本がそのまま対応する。

1
2
3

join . fmap join   ==  join . join     -- 結合律
join . fmap return ==  id              -- 単位律（右）
join . return      ==  id              -- 単位律（左）

そして、モノイドと並べると次の表になる。

モノイド $(M, \oplus, e)$	モナド $(T, \mu, \eta)$
集合 $M$	自己関手 $T$
二項演算 $\oplus: M \times M \to M$	自然変換 $\mu: T \circ T \Rightarrow T$（`join`）
単位元 $e \in M$	自然変換 $\eta: \mathrm{Id} \Rightarrow T$（`return`）
結合律 $(a \oplus b) \oplus c = a \oplus (b \oplus c)$	$\mu \circ T\mu = \mu \circ \mu T$
単位律 $e \oplus a = a = a \oplus e$	$\mu \circ T\eta = \mathrm{id}_T = \mu \circ \eta T$

「積」にあたるものが、モノイドでは集合の直積、モナドでは関手の合成に置き換わっているだけで、要求している法則はまったく同じ形をしている。「モナドは自己関手の圏におけるモノイド対象である」という有名な言い回しは、この表を一文にしたものだ。

自然変換がここで効いているのも重要な点だ。return :: a -> m a も join :: m (m a) -> m a も、型変数 a について多相であり、中身の値を見ないで書かれている。もし join が中身の型ごとに違う振る舞いをしてよいなら、fmap との交換が保証されず、法則を型をまたいで議論できない。自然変換という条件が、モノイド対象としての議論を成り立たせている。

まとめると、順番はこうなる。

モノイドは「結合的な演算と単位元」を持つ構造で、fold を安全に分割できる
関手に join（平坦化）を足すと、fmap と組み合わせて bind が作れる
その bind による合成が結合律と単位律を満たすものがモナドで、法則の形はモノイドと同じ
その一致は、join と return を自然変換と見ることで、正確な対応として言い直せる

アルゴリズムを関数型で考えると何が変わるか

ここまでの整理を踏まえると、命令型で書いていたアルゴリズムを関数型で考え直したときに、次のような変化が起きる。

1. ループが畳み込み（fold）になる

命令型では for ループと可変な累積変数で合計や最大値を求めることが多いが、関数型ではリストの畳み込みとして表現する。

1
2

sumList :: [Int] -> Int
sumList = foldr (+) 0

(+) と 0 はまさに前述のモノイドの演算と単位元にあたる。畳み込みの対象がモノイドであれば、計算の分割や並列化を安全に行える。

2. 逐次処理が関数合成・パイプラインになる

複数のステップを順に適用する処理は、代入と一時変数の列ではなく、関数合成として書ける。

1
2

process :: String -> String
process = normalize . validate . parse

各関数が純粋であれば、途中のステップを入れ替えたりテストしたりする際に、他のステップの実装や実行順序を気にする必要がない。合成の結合律が保証されているからだ。

3. 分割統治が不変データと自然に噛み合う

分割統治では、入力を部分問題に分け、それぞれを再帰的に解いて結合する。関数型言語ではデータが不変（immutable）であることが多く、部分問題同士が互いの状態を書き換える心配がない。マージソートのように「分割して、再帰的に解いて、結合する」アルゴリズムは、この不変性と相性がよい。

mergeSort :: Ord a => [a] -> [a]
mergeSort []  = []
mergeSort [x] = [x]
mergeSort xs  = merge (mergeSort left) (mergeSort right)
  where
    (left, right) = splitAt (length xs `div` 2) xs

4. 例外処理がモナドによる伝播になる

命令型では例外送出や戻り値のエラーチェックで異常系を扱うことが多いが、関数型では Maybe や Either のようなモナドに載せることで、正常系のロジックとエラー伝播を分離できる。

1
2

calc :: Int -> Int -> Maybe Int
calc a b = half a >>= \r -> recip100 (r + b)

途中で Nothing が出た時点で以降の計算はすべて Nothing として短絡する。if err != nil { return err } を各処理のあとに書き並べるのではなく、bind がその分岐をまとめて処理してくれる、と考えればわかりやすい。個々の関数は「失敗するかもしれない」ことだけを型で表現し、伝播の仕組み自体は bind に任せる。この分離によって、アルゴリズム本体のコードは「起こりうる失敗をどう伝えるか」ではなく「何を計算するか」に集中できる。

注意点

圏論のすべての概念が、実務でそのまま役立つわけではない。モナド則のような法則は、ライブラリの実装の信頼性を判断する基準として役立つ場面が中心になる
自作の Monad インスタンスを書く場合は、型が通っただけで満足せず、3 法則を具体値で確かめたほうがよい。Haskell なら QuickCheck、Scala なら Cats の MonadLaws のように、法則をテストする仕組みが用意されている
遅延評価や副作用のある言語（Haskell の IO を含む）では、圏論の理想的なモデルと実際の実行順序・パフォーマンス特性との間にずれが生じうる。理論と実装の違いは分けて考えたほうがよい
モナドは「文脈付きの計算をつなぐ仕組み」であって、常に複雑さを減らすとは限らない。単純な処理に無理にモナドを当てはめると、かえって読みにくくなる場合もある
圏論用語を導入するかどうかは、チームの前提知識に合わせて判断したほうがよい。用語がなくても map や flatMap の使い方自体は説明できる

参考

Mac Lane, S. “Categories for the Working Mathematician”. Springer, 1971
Bartosz Milewski. “Category Theory for Programmers”. 2018
Wadler, P. “Monads for functional programming”. 1995
Wadler, P. “Theorems for free!”. 1989
Haskell Wiki. “Typeclassopedia”
Haskell Wiki. “Monad laws”

関数型言語と圏論

圏・関手・モノイド・モナドから見る関数型プログラミング

関数型言語と圏論

結論

前提

圏論の基礎

圏・対象・射

射の種類（モノ射・エピ射・同型射）

合成の法則: 結合律と単位律

関手（functor）

自然変換（natural transformation）

なぜ「自然」と呼ぶのか

関数型言語と圏論の関係

型と関数の圏

純粋関数と参照透過性

モノイド（monoid）

定義

具体例で法則を確かめる

結合律が並列化を許す

モナド（monad）

「文脈付きの値」を繋ぐ

なぜ `map` だけでは足りないのか

`bind`、`flatMap`、`join` の関係

モナドの構成要素と法則

Maybe モナドで法則を展開する

IO モナドでの法則

そのほかのモナドでの法則

法則が破れるとき

モノイドとモナドはどうつながるのか

アルゴリズムを関数型で考えると何が変わるか

1. ループが畳み込み（fold）になる

2. 逐次処理が関数合成・パイプラインになる

3. 分割統治が不変データと自然に噛み合う

4. 例外処理がモナドによる伝播になる

注意点

参考

See also

関数型言語と圏論

結論

前提

圏論の基礎

圏・対象・射

射の種類（モノ射・エピ射・同型射）

合成の法則: 結合律と単位律

関手（functor）

自然変換（natural transformation）

なぜ「自然」と呼ぶのか

関数型言語と圏論の関係

型と関数の圏

純粋関数と参照透過性

モノイド（monoid）

定義

具体例で法則を確かめる

結合律が並列化を許す

モナド（monad）

「文脈付きの値」を繋ぐ

なぜ map だけでは足りないのか

bind、flatMap、join の関係

モナドの構成要素と法則

Maybe モナドで法則を展開する

IO モナドでの法則

そのほかのモナドでの法則

法則が破れるとき

モノイドとモナドはどうつながるのか

アルゴリズムを関数型で考えると何が変わるか

1. ループが畳み込み（fold）になる

2. 逐次処理が関数合成・パイプラインになる

3. 分割統治が不変データと自然に噛み合う

4. 例外処理がモナドによる伝播になる

注意点

参考

Share

See also

なぜ `map` だけでは足りないのか

`bind`、`flatMap`、`join` の関係