Haskell/圏論


この項目では Haskell に関連する内容に限って圏論の概観を与えることを試みる。そのために、数学的な定義に併せて Haskell コードも示す。絶対的な厳密さは求めない。そのかわり、圏論の概念とはどんなものか、どのように Haskell に関連するかの直感的な理解を読者に与えることを追求する。
本質的に、圏とは単純な集まりである。これは次の3つの要素からなる。
様々なものが圏をつくる。例えば、Set は全ての集合を対象とし、射として標準的な関数、合成として通常の関数合成を持つ圏である。(圏の名前はしばしば太字で表される。)Grpは全ての群を対象とし、射として群の演算を保存する関数(群準同型)を持つ圏である。つまり、任意の2つの群 G, H (それぞれ演算 ∗ {\displaystyle *} , ⋅ {\displaystyle \cdot } をもつ)について、 f ( u ∗ v ) = f ( u ) ⋅ f ( v ) {\displaystyle f(u*v)=f(u)\cdot f(v)} ならば、かつそのときに限り、 f : G → H {\displaystyle f:G\to H} は Grp 内の射である。
射はいつも関数のようにも思えるが、そうである必要はない。例えば、いかなる半順序 (P, ≤ {\displaystyle \leq } )も圏を定義する。ここで対象はPの要素であり、任意の2つの対象A, Bについて A ≤ B {\displaystyle A\leq B} であるときかつそのときに限りAとBの間に射が存在する。また、複数の異なる射が同じソースオブジェクトとターゲットオブジェクトを持つことができる。Setの例でいえば、 sin {\displaystyle \sin } と cos {\displaystyle \cos } はいずれもソースオブジェクト R {\displaystyle \mathbb {R} } と ターゲットオブジェクト [ − 1 , 1 ] {\displaystyle [-1,1]} をもつが、もちろんこれらは同じ射ではない!

圏が従わなければならない規則が3つ存在する。最初に、非常に単純だが、射の合成は結合的である必要がある。つまり、
次に、圏は合成演算において閉じていなければならない。すなわち、もし f : B → C {\displaystyle f:B\to C} かつ g : A → B {\displaystyle g:A\to B} ならば、 h = f ∘ g {\displaystyle h=f\circ g} のような射 h : A → C {\displaystyle h:A\to C} がその圏に存在しなければならない。次の圏を使えば、これがどのように働くかを見ることができる。
f と g はどちらも射であるので、これらを合成したらこの圏にあるいずれかの射を得るはずである。では、どれが射 f ∘ g {\displaystyle f\circ g} だろうか?唯一の答えは i d A {\displaystyle {\mathit {id}}_{A}} である。同様に g ∘ f = i d B {\displaystyle g\circ f={\mathit {id}}_{B}} もわかる。
最後に、いかなる対象 A についても恒等射 i d A : A → A {\displaystyle {\mathit {id}}_{A}:A\to A} 、すなわちその射との合成が恒等であるような射が圏 C に存在しなければならない。正確に言えば、任意の射 g : A → B {\displaystyle g:A\to B} に対して
である。

この項目で我々が考えようとしている主な圏は、Haskellの型を対象とし、Haskell の関数を射とし、合成として(.)を使う圏 Hask である。型 A から Bの関数 f :: A -> B は Hask の射である。 この定義が最初の2つの規則を満たすことは容易に確認できる。 すなわち(.) は結合的であり、また任意の f と gについて f . g は明らかに何らかの関数である。Hask における恒等射は id であり、次は自明である。

ただし、これは添え字を欠いてしまっており、上記の規則の厳密な翻訳ではない。Haskell の関数 id は 多相的である。すなわちその定義域や値域に異なる様々な型をとることができる、もしくは圏で言い換えれば、異なるソース及びターゲットオブジェクトをとることができる。しかし圏論における射は単相的である。すなわちどんな射もソースオブジェクトとターゲットオブジェクトを1つずつ指定して定義される。多相な Haskell 関数はその型を明示することによって単相化することができる(単相型によるインスタンス化)ため、『Hask圏の型Aに対する恒等射は(id :: A -> A)である』と書けばより正確になる。これを考慮すると、先程の則は次のように書き直せる。

しかしながら議論を単純にするため、意味が明らかであるときはこの違いを無視することにする。

対象と対象を関連付ける射を持つ幾つかの圏を見てきた。圏論の次の大きな話題は圏どうしを関連づける関手(functor、ファンクタ)である。関手の本質は圏の間の変換である。つまり圏C と Dが与えられたとき、関手 F : C → D {\displaystyle F:C\to D} は次のことをする。
関手の好例のひとつは忘却関手(forgetful functor) G r p → S e t {\displaystyle \mathbf {Grp} \to \mathbf {Set} } である。これは群をその内在する集合に対応付け、群の射を同様に振る舞うがしかし群の代わりに集合の上で定義される関数に対応付ける。他の例としては冪集合関手 S e t → S e t {\displaystyle \mathbf {Set} \to \mathbf {Set} } がある。これは集合をその冪集合に対応付け、関数 f : X → Y {\displaystyle f:X\to Y} を関数 P ( X ) → P ( Y ) {\displaystyle {\mathcal {P}}(X)\to {\mathcal {P}}(Y)} 、つまり U ⊂ X {\displaystyle U\subset X} をとり f ( U ) = { f ( u ) | u ∈ U } {\displaystyle f(U)=\{\,f(u)|u\in U\,\}} と定義される、 f の下の U の像を返す関数にそれぞれ対応付ける。あらゆる圏 C について、C上の恒等関手として知られる関手、すなわち対象や射をそれ自身に対応付ける、 1 C : C → C {\displaystyle 1_{C}:C\to C} を定義できる。これは後のモナド則の節で便利であることがじきにわかるであろう。
関手が従わなければならない幾つかの公理を挙げておこう。最初に、任意の対象 A 上の恒等射 i d A {\displaystyle id_{A}} について、 F ( i d A ) {\displaystyle F(id_{A})} は恒等射でなければならない。

ふたつめに、関手は射の合成を分配しなければならない。
Haskellでお目にかかったことがあるかもしれない型クラス Functor は、実際に圏論における関手の概念と一致する。関手がふたつの構成要素からなることを思い出そう。関手はある圏の対象を別の圏の対象に対応付け、最初の圏の射をふたつめの圏の射に対応付ける。Haskell の関手は Hask から funcである。ここで func は関手の型の上でちょうど定義されるHaskの部分圏である。例えばリスト関手は Hask から Lstである。ここでLstはリスト型、すなわち任意の型Tに対するリスト型[T]のみを含む圏である。Lstにおける射はリスト型の上で定義される関数であり、これは任意の型T, Uに関して [T] -> [U]の関数である。どのようにこれを Haskell のFunctor型クラスへと結びつけたらよいのであろうか?定義を思い出そう。
インスタンスの例も示しておこう。
ここが鍵となる部分である。型構築子 Maybe は任意の型 T をとり新たな型Maybe Tとなる。また、Maybe 型へと狭められた fmap は関数 a -> b をとり関数 Maybe a -> Maybe b を返す。まさにこれがまさにそうではないか!ふたつの構成要素を定義した。ひとつはHaskの対象をとり別の圏(これはMaybe型を対象、Maybe型上の関数を射とする)の対象を返す何か、もうひとつはHask の射をとりこの圏の射を返す何か。ゆえに Maybe は関手である。
Haskellの関手が内容に関してmapできるような型を表すということは有用な直観である。これはリストや Maybeだけでなく、木のようなより複雑な構造もそうである。構造の内容にmapを行う関数はfmapを使って書くことができ、どんな関手構造もこの関数に渡すことができる。例えば、Data.List.map, Data.Map.map, Data.Array.IArray.amap などをすべてをカバーするジェネリックな関数を書くことができる。
関手の公理はどうだろうか?任意のAに対する i d A {\displaystyle id_{A}} として多相的な関数 id を使い、最初の則は次のように書ける。
先程の直観によると、この式は『構造を辿ってしかし各要素に何もしないmapと、全く何もしないことは等しい」と解釈できる。次に、射の合成は単に (.) であり、つまり、
このふたつめの則は実用的に極めて役に立つ。関手をリストか何かのコンテナと考えると、右辺は2パスのアルゴリズムを表す。つまり構造についてまずgをmapし、さらにfをmapする。この関手の公理はこのような2パスのアルゴリズムをf . gを行う1パスのアルゴリズムへと変換できることを保証する。この処理は 融合(fusion)として知られている。
関手はどのように圏論が Haskell へと変換されるかの良い例を提供する。次が理解の鍵となる。


モナドは言うまでもなく Haskell の極めて重要な概念であるが、実はこれらは本来圏論に由来するものである。モナド は圏から同じ圏への関手であり、さらにいくつかの追加の構造を提供する。では定義を見てみよう。モナドはC内のすべての対象 Xに対してふたつの射をともなう関手 M : C → C {\displaystyle M:C\to C} である。
議論されているモナドが明らかなとき、これらの関数について上添字 M を省略することにし、単に何らかの X に対する u n i t X {\displaystyle {\mathit {unit}}_{X}} と j o i n X {\displaystyle {\mathit {join}}_{X}} について述べることにする。
では、どのようにこれを Haskell の型クラス Monad に翻訳されるかをみよう。
このクラス制約Functor mはmがあらかじめ関手の構造、つまり対象と射の対応付けを持っていることを保証する。return は全ての X に対する u n i t X {\displaystyle {\mathit {unit}}_{X}} の(多相的な)類義語である。しかしここには問題がある。returnの型はunitに非常に似ているけれども、もう一方の関数、しばしばbindとも呼ばれる (>>=)の型はjoinに似ていない。ここでさらに別のモナド関数join :: Monad m => m (m a) -> m aがあり、これは非常によく似ている。実際に、join と (>>=)は次のように互いに表すことができる。

つまり、モナドの return, fmap, joinを定義することは、return と (>>=)を定義することと同等である。圏論でモナドの定義をする典型的な方法がunit と joinを与えることであるのに対して、Haskell プログラマはreturn と (>>=)を与えることを好むことがわかる。多くの場合、圏論の方法のほうが理にかなっている。 何らかの構造 M {\displaystyle M} があり、任意の対象Xを M ( X ) {\displaystyle M(X)} としたり、 M ( M ( X ) ) {\displaystyle M(M(X))} を M ( X ) {\displaystyle M(X)} とできる自然な方法があるとき、それはしばしばモナドである。次の節で例を示す。

先ほど述べた冪集合関手 P : S e t → S e t {\displaystyle P:\mathbf {Set} \to \mathbf {Set} } はモナドをなす。任意の集合Sについて、要素をその単集合へ写す u n i t S ( x ) = { x } {\displaystyle {\mathit {unit}}_{S}(x)=\{x\}} がある。これらの単集合のそれぞれは明らかに S の部分集合であり、よって u n i t S {\displaystyle {\mathit {unit}}_{S}} はSの冪集合の要素を返す、つまりモナドの要求を満たしている。同様に関数 j o i n S {\displaystyle {\mathit {join}}_{S}} を次のように定義できる。引数として L ∈ P ( P ( S ) ) {\displaystyle L\in {\mathcal {P}}({\mathcal {P}}(S))} をとる。これは、
よって j o i n S {\displaystyle {\mathit {join}}_{S}} はこれらの部分集合の和を返すことで、Sのまた別の部分集合を与えるようにする。式で表せば、
従って、(次の節で探求する規則を満たすことが証明できれば)P はモナドである。
実際のところ、議論の対象が集合の代わりにリストになるという違いを除けば、Pはほとんどリストモナドと等しい。これらはほぼ同じものである。比較してみよう。

関手がそう呼ばれるためには従わなければならない公理があるように、モナドにも幾つかそのような公理が存在する。まずはそれらを一覧し、次に Haskell へと翻訳し、なぜそれが重要なのかをみていくことにしよう。
モナド M : C → C {\displaystyle M:C\to C} と、 A , B ∈ C {\displaystyle A,B\in C} に射 f : A → B {\displaystyle f:A\to B} があるとする。 このとき次が成り立たなくてはならない。
Haskell への翻訳はなるべく自明であってほしい。
(fmap が関手の構成要素のひとつで、射に作用するものであることを思い出そう。)これらの則は最初は少し不可解にも思える。いったいこれらの則はどういう意味で、なぜモナドはこれを満たすべきなのだろうか?ではこれらの法則について調べていこう。
join . fmap join = join . join
この規則を理解するために、まずはリストの例を使っていこう。最初の規則はjoin . fmap join (左辺) と join . join (右辺)のふたつの関数について述べている。これらの型はどうなるだろうか?(今はリストモナドについて議論しているので)joinの型は[[a]] -> [a]であることを思い出そう。つまり両辺の型はどちらも[[[a]]] -> [a]である。(これが同じであるという事実は役に立つ。最終的には、両辺が全く同じ関数であることを示そうとしているのだ。)では、リストのリストのリストがあるとしよう。左辺はこの三重のリストに fmap joinを作用させ(1)、その結果に join を適用する(2)。 fmap はリストに対しては map と同じであるので、(1)の計算はまずいちばん外側のリストの要素に対してjoinをmapで施す。各要素に対して、joinはリストのリストそれぞれを連結する。結果としてリストのリストが得られたら、(2)によりこれ全体にjoinを適用する。手短に言えば、トップレベルに'入り込み'、二番目と三番目のレベルを潰してひとつにして、次いでトップレベルとこの新しいレベルを潰してひとつにする。
では右辺についてはどうだろうか?最初にリストのリストのリストに対して join を実行する。普通joinは二重のリストに適用するものであるが、三重のリストにも適用できる。なぜなら、[[[a]]]はb = [a]とおけば[[b]]と書けるからである。つまり三重のリストはある意味で二重のリストにすぎない、ただし最深部は'フラット'な値でなく別のリストからなっている。だからもしリストのリスト(のリスト)にjoinを適用すると、外側のふたつのリストがひとつに平坦化される。外から二番目の深さのリストの要素はフラットではなく三番目の層のリストが含まれているので、この結果はリストのリストであり、次にもう一方のjoin がこの構造を平坦化する。要約すると、左辺は内側のふたつの層を新しい層へと平坦化し、それから最も外側と新しい層を平坦化する。右辺は外側のふたつの層をまず平坦化し、それから新しい層と最も内側の層を平坦化する。これらの二つの操作は等しい。これはいわばjoinに関する結合則のようなものである。
次のようにしたMaybe もまたモナドである。
三重の Maybe (これはNothing, Just Nothing, Just (Just Nothing), Just (Just (Just x))といった値をとる)を考えて、一つめの規則は内側のふたつの層を先に潰し、それから外側の層を潰すことは、外側の層が先に潰し、それから最も内側の層を潰すことと全く同じであると述べている。
join . fmap return = join . return = id
それでは、二番目の法則はどうだろうか?再び、リストの例で始めよう。二番目の法則で述べられている両辺は [a] -> [a]の関数である。左辺はまずリストのそれぞれの要素xを要素がそれひとつだけのリスト[x]へと変え、シングルトンリストのリストを得る。この二重のリストは再びjoinを使って一重のリストへと平坦化される。以上が左辺の表す関数である。一方右辺では、リスト全体[x, y, z, ...]をとり、これをリストのシングルトンリスト[[x, y, z, ...]]にし、それから再びこのふたつの層をひとつに平坦化する。この規則は一言で説明できるほどの自明さはないが、returnをモナドの値に適用しその結果をjoinすることは、returnを最上位の層の内側で実行しても外側で実行しても同じ結果になるべきであるということを本質的に述べている。

return . f = fmap f . return
join . fmap (fmap f) = fmap f . join
最後のふたつの法則は、どのようにモナドが振舞うべきかに関するもっと自明な事実を示す。これがどう真であるかを調べる最も簡単な方法は、展開した形式を使うためにこれらを展開することである。
モナドが従わなければならない規則について直観的に説明した。ではなぜこれは重要なのか?その答えは do ブロックについて考えたときに明らかになる。次のお決まりの変換が示しているように、do ブロックが文の組み合わせを(>>=)を使わずに表すためのただの構文糖衣であることを思い出そう。
ここで用いている4つの規則から、通常の return と(>>=)を使ったモナド則を証明できることに注意したい。(非常に大掛かりな証明もあるので、ここは飛ばしてしまっても構わない。)

returnと(>>=)を使うこの新たなモナド則は、これをdo記法へと変換できる。

モナド則はいまやdoブロックがどのように機能すべきかという常識を述べた文である。もしこれらの規則がひとつでも無効であれば、doブロックを期待したとおりに操作できなくなるのでユーザが混乱する。要するに、モナド則はユーザビリティガイドラインなのである。

この章で長い道のりを辿ってきた。圏とは何か、どうやってHaskellに応用されるのかを見てきた。関手をはじめとする圏論の基本的な概念から、モナドのようなより発展的な内容まで、それらがいかにHaskellらしさに必要不可欠であるかについても紹介してきた。自然変換(natural transformations)など、我々の目的に必要なかった幾つかの圏論の基本的事項については触れなかったが、代わりにHaskellの構造の背後に根付く圏論の直観的な理解を提供した。

テンプレート:Haskell navigation