関数型言語と圏論

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

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

この記事では、圏論の基本要素を体系的に整理したうえで、関数型言語の特徴が圏論のどの概念に対応するかをまとめる。そして最後に、アルゴリズムを関数型的に考えると設計がどう変わるかを見ていく。

結論

圏とは、対象と射の集まりであり、射の合成が結合律と単位律を満たすものをいう
関数型言語の型はおおむね圏の対象、関数はおおむね圏の射に対応する。この対応のおかげで、関数合成の性質を圏論の法則として議論できる
ファンクターは圏から圏への構造を保つ写像で、プログラミングでは map を持つ型として現れる
モノイドは「結合的な二項演算」と「単位元」を持つ代数構造で、リストの連結や数値の加算はすべてモノイドの具体例
モナドはファンクターに flatten（合成可能な bind）を加えたもので、失敗・非同期・状態のような「文脈付きの計算」を関数合成の形で扱うための枠組み
関数型でアルゴリズムを考えると、ループは畳み込みに、逐次処理は関数合成に、例外処理はモナドによる伝播に置き換わることが多い

前提

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

圏論の基礎

圏・対象・射

圏（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)

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

自然変換（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

自然変換は初学者には抽象度が高く感じられやすいが、プログラミングでは「ある型を別の型に変換する、実装に依存しない一様な関数」として現れる。たとえば Maybe a -> [a]（値があれば単一要素のリストに、なければ空リストに変換する関数）は自然変換の一例だ。

なぜ「自然」と呼ぶのか

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

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

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

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

関数型言語と圏論の関係

型と関数の圏

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

圏論の概念	プログラミングでの対応
対象	型（`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 つだけの圏として捉えることもできる。射の合成が二項演算に、恒等射が単位元に対応する。

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

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

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

class Monoid m where
  mempty  :: m
  mappend :: m -> m -> m

instance Monoid [a] where
  mempty  = []
  mappend = (++)

モノイドの利点は、要素の並べ方を問わず並列に集約できることだ。結合律が保証されているため、fold の計算順序を分割・並列化しても結果が変わらない。ログの集計やイベントの集約処理を並列化しやすい設計にできるのは、この法則のおかげだ。

モナド（monad）

モナドは、ファンクター（map が使える型）に、入れ子になった文脈を平坦化する操作を加えたものだ。次の 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$ という形の関数）」の圏として整理できる。この見方では、return が恒等射、bind を使った合成が Kleisli 圏における射の合成になる。モナド則がモノイド則と同じ見た目をしているのは偶然ではなく、モナドが「Kleisli 圏における恒等射と合成が満たすべき、圏の法則そのもの」だからだ。

具体例として、失敗しうる計算を Maybe で表すと、次のようにエラー伝播を関数合成として書ける。

safeDivide :: Int -> Int -> Maybe Int
safeDivide _ 0 = Nothing
safeDivide x y = Just (x `div` y)

calc :: Int -> Int -> Int -> Maybe Int
calc a b c =
  safeDivide a b >>= \r1 ->
  safeDivide r1 c

途中で Nothing が出た時点で以降の計算はすべて Nothing として短絡する。if err != nil { return err } を各処理のあとに書き並べるのではなく、bind がその分岐をまとめて処理してくれる、と考えればわかりやすい。

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

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

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 のようなモナドに載せることで、正常系のロジックとエラー伝播を分離できる。個々の関数は「失敗するかもしれない」ことだけを型で表現し、伝播の仕組み自体は bind に任せる。この分離によって、アルゴリズム本体のコードは「起こりうる失敗をどう伝えるか」ではなく「何を計算するか」に集中できる。

注意点

圏論のすべての概念が、実務でそのまま役立つわけではない。モナド則のような法則は、ライブラリの実装の信頼性を判断する基準として役立つ場面が中心になる
遅延評価や副作用のある言語（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
Haskell Wiki. “Typeclassopedia”

関数型言語と圏論

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

関数型言語と圏論

結論

前提

圏論の基礎

圏・対象・射

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

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

関手（functor）

自然変換（natural transformation）

なぜ「自然」と呼ぶのか

関数型言語と圏論の関係

型と関数の圏

純粋関数と参照透過性

モノイド（monoid）

モナド（monad）

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

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

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

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

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

注意点

参考

See also

関数型言語と圏論

結論

前提

圏論の基礎

圏・対象・射

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

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

関手（functor）

自然変換（natural transformation）

なぜ「自然」と呼ぶのか

関数型言語と圏論の関係

型と関数の圏

純粋関数と参照透過性

モノイド（monoid）

モナド（monad）

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

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

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

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

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

注意点

参考

Share

See also