🗣️

クライスリ・トリプルといくつかの例

2023/05/20に公開

クライスリ・トリプル

クライスリ・トリプル とは次の3つの組み合わせです。

  • 自己関手 T
  • 拡張演算子 (\_)^{\#}
  • 自然変換 \eta

拡張演算子は任意の f : X \rightarrow T Y について f^{\#} : TX \rightarrow TY を割り当てます。f : X \rightarrow T Y という射の(domain)XTX拡張しているわけです。

拡張は f : X \rightarrow TYg : Y \rightarrow T Z を合成するために必要です。このままでは f余域(codomain)と g の域が等しくありませんので、合成ができません。そこで、gg^{\#} に拡張するわけです。すると、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 YC 上の射 f : X \rightarrow TY
  • 合成: X \xrightarrow{f} Y \xrightarrow{g} Z の合成 g \circ fC 上の 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 \rightarrow Y + 1

と考えるということです。つまり、排他的論理和

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 を以下のように定めます。

\eta_X (x) = x

つまり、恒等写像を疑似部分写像にしたものです。拡張 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 は単元集合を返します。

\eta_X (x) = \{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

です。これにも多価関数と同様なクライスリ・トリプルを与えられます。単位元は、

\eta_X (x) = (x)

です。つまり、長さ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(a, x) = f_a(x)

と考えるわけです。添字集合が固定されているとして、たとえば、f : \Sigma \times X \rightarrow Yg : \Sigma \times Y \rightarrow Z を合成したいときに積余クライスリ・トリプルがそれを可能にします。

余単位元 \varepsilon_X : \Sigma \times X \rightarrow X射影です。つまり、

\varepsilon_X(a, x) = x

です。これは任意の添字 a \in \Sigma について (\varepsilon_{X})_a = \mathrm{id}_X ということです。余拡張は

f^{\dagger}(a, x) = (a, f(x))

になります。合成するときは、前後で同じ添字を使うことになります。余クライスリ圏では、
f : X \rightarrow Yg : Y \rightarrow Z の合成 g \circ f : X \rightarrow Z は、任意の a \in \Sigma について、

(g \circ f)_a = g_a \circ f_a

を考えているということです。

参考文献

GitHubで編集を提案

Discussion