クライスリ・トリプル
クライスリ・トリプル とは次の3つの組み合わせです。
- 自己関手 T
- 拡張演算子 (\_)^{\#}
- 自然変換 \eta
拡張演算子は任意の f : X \rightarrow T Y について f^{\#} : TX \rightarrow TY を割り当てます。f : X \rightarrow T Y という射の域（domain）X を TX に拡張しているわけです。
拡張は f : X \rightarrow TY と g : Y \rightarrow T Z を合成するために必要です。このままでは f の余域（codomain）と g の域が等しくありませんので、合成ができません。そこで、g を g^{\#} に拡張するわけです。すると、g^{\#} \circ f : X \rightarrow TY という合成を考えられる。
自然変換 \eta は単位元と呼ばれます。というのは、拡張によって得られる合成について単位元となるからです。まず、\eta は次のような自然変換です。つまり、任意の C の対象 X について、
\eta_X : X \rightarrow TX
という射を定める。そして、任意の f : X \rightarrow TY について、
f^{\#} \circ \eta_X = f = \eta_Y^{\#} \circ f
が成り立ちます。等式 f = \eta_Y^{*} \circ f はいささか冗長です。これは、
\eta_{Y}^{\#} = \mathrm{id}_{TY}
が与えられれば十分です。
また、拡張によって得られる合成は結合的です。つまり、
h^{\#} \circ (g^{\#} \circ f) = (h^{\#} \circ g)^{\#} \circ f
です。これもいささか冗長です。そもそも関数合成 \circ は結合的ですから、
h^{\#} \circ g^{\#} = (h^{\#} \circ g)^{\#}
が与えられば十分です。クライスリ・トリプルの公理を以下のようにまとめましょう。
-
右単位元則： f^{\#} \circ \eta_X = f
-
左単位元則： \eta_Y^{\#} = \mathrm{id}_{TY}
-
結合法則： h^{\#} \circ g^{\#} = (h^{\#} \circ g)^{\#}
関数型プログラミングにおけるクライスリ・トリプル
単位元 \eta と拡張演算子 (\_)^{\#} は Haskell の return と >>= に対応します。
return :: a -> m a
>>= f :: m a -> m b
ただし、f :: a -> m b です。
クライスリ圏
クライスリ・トリプル \lang T, (\_)^{\#}, \eta \rang が与えられたとします。このとき、次のように クライスリ圏 と呼ばれる圏を考えられます。
- 対象： C の対象と等しい
- 射： f : X \rightarrow Y は C 上の射 f : X \rightarrow TY
- 合成： X \xrightarrow{f} Y \xrightarrow{g} Z の合成 g \circ f は C 上の X \xrightarrow{f} TY \xrightarrow{g^{\#}} TZ の合成 g^{\#} \circ f
部分写像
写像 f : X \rightarrow Y とは任意の x \in X について f(x) \in Y が一意に定まるときに与えられます。しかし、ある x \in X については f(x) \in Y が定まらないということもあるでしょう。これを部分写像（partial mapping）といいます。
これを全域で定義された写像と考える方法があります。それが、
と考えるということです。つまり、排他的論理和
f(x) \in Y \oplus f(x) \in 1
が成り立ちます。定まらないときは、f(x) = 0 としてしまうわけです（1 = \{0\}）。しばしば、f(x) = \bot と表します。以降はこちらの記法にしましょう。
単位元 \eta は任意の X について \eta_X : X \rightarrow X + 1 を以下のように定めます。
つまり、恒等写像を疑似部分写像にしたものです。拡張 f^{\#} : X + 1 \rightarrow Y + 1 は、
f^{\#} (x) =
\begin{cases}
f(x) & \cdots& x \in X\\
\bot & \cdots& x = \bot
\end{cases}
部分写像ですから、未定義の値を受け取ればそれを未定義として返すわけです。このクライスリ圏は部分写像の圏となります。
関数型プログラミングでは Maybe モナドに等しいです。
data a = Nothing | Just a
多価関数
続いては f(x) \in Y が一意に定まらないときを考えます。つまり、f(x) が複数あるようなときです。こちらも、一意写像と考える方法があります。それが、
f(x) : X \rightarrow \mathcal{P} Y
を考えるという方法です。 ただし、\mathcal{P} はべき（power）です。つまり、部分集合全体を余域とするわけです。f(x) \in Y ではなく f(x) \subseteq Y となります。
単位元 \eta_X : X \rightarrow \mathcal{P}X は単元集合を返します。
こちらも恒等写像を擬似多価関数にしたものと考えればよいでしょう。拡張 f^{\#} : \mathcal{P}X \rightarrow \mathcal{P}Y は、
f^{\#} (X') = \bigcup_{x \in X'}f(x)
になります。受け取った複数の値に対して f(x) の和集合を返すわけです。このクライスリ圏は多価関数の圏になります。
多価関数は二項関係 R \subseteq X \times Y でもあります。そのため、このクライスリ圏は関係の圏でもある。このことについては、また別の記事で詳しく書く予定です。
列（リスト）
多価関数の場合は返値が集合でした。集合とは順序のない集まりと考えられます。つまり、\{x, y\} = \{y, x\} です。さらに重複も無視します。つまり、\{x, y, y\} = \{x, y\} です。さて、順序もあり重複も無視しないものを列（list）と呼びます。x \in X の列全体をX^{*} と表しましょう。これは直積の閉包
X^{*} = 1 + X + X^2 + X^3 + \cdots
です。これにも多価関数と同様なクライスリ・トリプルを与えられます。単位元は、
です。つまり、長さ1の列に返すわけです。そして、f^{\#} : X^{*} \rightarrow Y^{*} は、
f^{\#} (x_1, x_2, \cdots, x_n) = (f(x_1), f(x_2), \cdots, f(x_n))
です。
余クライスリ・トリプル
クライスリ・トリプルの双対を考えることができます。それが、余クライスリ・トリプルです。
- 自己関手 D
- 余拡張演算子 (\_)^{\dagger}
- 自然変換 \varepsilon
余拡張演算子は余域を拡張します。つまり、f : DX \rightarrow Y について、
f^{\dagger} : DX \rightarrow DY
を与えます。余拡張によって得られる合成は、
g \circ f^{\dagger} : DX \rightarrow Z
です。余クライスリ・トリプルの公理は、
-
右単位元則： \varepsilon_X^{\dagger} = \mathrm{id}_{DX}
-
左単位元則： \varepsilon_Y \circ f^{\dagger} = f
-
結合法則： h^{\dagger} \circ g^{\dagger} = (h^{\dagger} \circ g)^{\dagger}
積
任意の a \in \Sigma について f_a : X \rightarrow Y が定まるとします。つまり、\Sigma が添字集合（index set）となっているわけです。これを f : \Sigma \times X \rightarrow Y と考えることができます。つまり、
と考えるわけです。添字集合が固定されているとして、たとえば、f : \Sigma \times X \rightarrow Y と g : \Sigma \times Y \rightarrow Z を合成したいときに積余クライスリ・トリプルがそれを可能にします。
余単位元 \varepsilon_X : \Sigma \times X \rightarrow X は射影です。つまり、
です。これは任意の添字 a \in \Sigma について (\varepsilon_{X})_a = \mathrm{id}_X ということです。余拡張は
f^{\dagger}(a, x) = (a, f(x))
になります。合成するときは、前後で同じ添字を使うことになります。余クライスリ圏では、
f : X \rightarrow Y と g : Y \rightarrow Z の合成 g \circ f : X \rightarrow Z は、任意の a \in \Sigma について、
(g \circ f)_a = g_a \circ f_a
を考えているということです。
参考文献
Discussion