Chapter 44

14.2 表現可能関手

さのたけと
さのたけと
2021.06.02に更新

これまで、\mathbf{C}のどんな対象aの選択についても、\mathbf{C}から\mathrm{Set}への関手が得られることを見てきた。このような、\mathrm{Set}への構造を保存するような写像はしばしば 表現(represenatation) とよばれる。今回は、\mathbf{C}の対象と射を\mathrm{Set}の集合と関数として表現している。

関手\mathbf{C}(a, -)それ自身のことがしばしば表現とよばれる。もっと一般的に、aの適当な選択についてそのHom関手と同型であるような関手F表現可能(representable) とよばれる。\mathbf{C}(a, -)\mathrm{Set}値なので、表現可能な関手は必ず\mathrm{Set}値でなければならない。

以前、同型な集合たちは同一であるとしばしば考えるということを言った。もっと一般的に、ある圏で同型な 対象 たちは同一であると考える。なぜなら、対象は射を通した他の対象への(あるいは自身への)関係以外に構造を何も持たないからである。

例えば、以前モノイドの圏\mathrm{Mon}の話をした。モノイドの圏は元々は集合でモデル化されていたのだった[1]。しかし、射としてそれら集合の間のモノイド構造を保つような関数だけを丁寧に選んだのだった。なので、\mathrm{Mon}の2つの対象が同型であれば、つまりそれらの間に可逆射が存在すれば、それらは完全に同じ構造なのである。対象や射のもととなった集合や関数の中身を覗き見たなら、あるモノイドの単位元がもう1つのモノイドの単位元に写り、2つの元の積がそれら2つを写したものの積に写っているさまが見られるだろう。

同じ推論が関手にも適用できる。2つの圏の間の関手たちは、自然変換が射の役割を果たすような圏をなす。なので、それらの間に可逆な自然変換が存在するならそれら2つの関手は同型であり、さらに同一のものであると思うことができる。

この観点から表現可能関手の定義を分析してみよう。Fが表現可能であるためには次が必要だった: \mathbf{C}の元a\mathbf{C}(a, -)からFへの自然変換\alpha、逆方向のもう1つの自然変換\betaが存在し、それらの合成が恒等自然変換であること。

対象xでの\alphaの要素に注目しよう。これは\mathrm{Set}での関数

\alpha_x \mathtt{::}\ \mathbf{C}(a, x) \to F x

である。この変換の自然性条件は、xからyへの任意の射fについて、次の図式

F f \circ \alpha_x = \alpha_y \circ \mathbf{C}(a, f)

が可換であると教えてくれる。Haskellでは、自然変換はオプションでforall量化子をつけた多相関数で置き換えられる:

alpha :: forall x. (a -> x) -> F x

自然性条件

fmap f . alpha = alpha . fmap f

は、左側のfmapは関手Fによって定義されており、右側のfmapはReader関手で定義されているという了解のもとで、パラメトリシティ(parametricity)のおかげで自動的に満たされる(以前に述べた無料の定理の1つだ)。Readerのfmapはただの関数合成なので、もっと明示的にすることができる。\mathbf{C}(a, x)の元hに作用しているとすると、自然性条件は次のように簡単化される:

fmap f (alpha h) = alpha (f . h)

もう一方の変換\betaは逆方向に行く:

beta :: forall x. F x -> (a -> x)

これは自然性条件を満たさなければならないし、\alphaの逆でなければならない:

alpha . beta = id = beta . alpha

あとで、\mathbf{C}(a, -)から任意の\mathrm{Set}値関手への自然変換は、F aが空でない限り常に存在する(米田の補題)が、それは必ずしも可逆ではないことを見よう。

リスト関手とaとしてのIntを使って、Haskellでの例を与えよう。ここで自然変換が仕事をする:

alpha :: forall x. (Int -> x) -> [x]
alpha h = map h [12]

ここで任意の数として12を取り、それで1要素のリストを作った。これで、このリストに渡って関数hfmapし、hの返り値の型のリストが得られる(実際はリストにある整数の個数だけこんな変換が起こる)。

ここでの自然性条件はmap(リスト版のfmap)の合成可能性と等価である:

map f (map h [12]) = map (f . h) [12]

しかし、逆変換を見つけようとすると、それは任意の型xのリストからxを返す関数に行くものであるはずである。

beta :: forall x. [x] -> (Int -> x)

例えばheadなんかを使ってリストからxを回収することが思い付くかもしれないが、これは空リストの場合にうまく行かない。型a(Intの代わりだった)については、うまく行くような選択肢はないことに注意しよう。したがって、リスト関手は表現可能ではない。

Haskellの(自己)関手はコンテナにちょっと似ているという話をしたのを覚えているだろうか?同じように、表現可能関手は関数呼び出しをメモ化した結果を蓄えるためのコンテナであると思うことができる(HaskellでのHom集合の元はただの関数である)。表現する対象、すなわち\mathbf{C}(a, -)での型aは、表でキーになる型と思うことができ、これを使って関数の値が集計された表にアクセスできる。先程まで\alphaとよんでいた変換はtabulate(表にする)とよばれ、その逆\betaindexとよばれる。これが(少し簡略化された)Representableクラスの定義である:

class Representable f where
    type Rep f :: *
    tabulate :: (Rep f -> x) -> f x
    index    :: f x -> Rep f -> x

表現型(さっきのa、ここではRep fとよぶ)は、Representableの定義の一部である。星は単にRep fは型であるという意味である(型コンストラクタや、もっと見慣れないカインドなんかではない)。

無限リスト、あるいはストリームは空ではなく、表現可能である。

data Stream x = Cons x (Stream x)

これはIntegerを引数として取る関数のメモ化された値たちと思うことができる(厳密に言うと非負自然数を使うべきだが、コードを複雑にしたくなかった)。

そのような関数をtabulateするには、値の無限ストリームを作ることになる。もちろん、これはHaskellが遅延評価のある言語だから可能になっている。値は必要なときにはじめて評価される。メモ化された値にはindexを使ってアクセスできる:

instance Representable Stream where
    type Rep Stream = Integer
    tabulate f = Cons (f 0) (tabulate (f . (+1)))
    index (Cons b bs) n = if n == 0 then b else index bs (n - 1)

任意の返り値の関数の族全体をカバーするようなメモ化のための枠組みを単一のものとして実装できるというのはとても面白いことだ。

反変関手の表現可能性は、\mathbf{C}(-, a)の2番目の引数を固定しておくことを除けば同様に定義できる。または等価なことだが、\mathbf{C}^{op}から\mathrm{Set}への関手を考えてもよい。なぜなら、\mathbf{C}^{op}(a, -)\mathbf{C}(-, a)と同じだからである。

表現可能性には面白いヒネリがある。カルテジアン閉圏では、Hom集合は内部で羃対象として扱えることを思い出そう。Hom集合\mathbf{C}(a, x)x^aと等価であり、表現可能関手については-^a = Fと書ける。

面白そうなので、両側で対数を取ってみよう: a = \mathrm{log}F

もちろん、これは全く形式的な変形だけれど、対数の性質をいくらか知っていればこれは極めて役に立つ。特に、直積型をもとにした関手は直和型で表現できることや、直和型の関手は一般には表現可能ではない(例: リスト関手)ことがわかる[2]

最後に、表現可能関手は同じ事柄の2つの異なる実装を与えることに注意しよう---1つは関数、1つはデータ構造である。それらは完全に同じ内容を持っている---同じ値が同じキーを使うと回収できる。これが私が話していた「同じさ」の感覚である。2つの自然同型な関手は、その内容に関わる限り同一視できる。他方、2つの表現はしばしば異なる風に実装され、異なる性能特性を持っているかもしれない。メモ化は性能向上に使われ、実行時間を劇的に削減するのにつながるかもしれない。根底が同じ計算の異なる表現を生成できるというのは実践上とても価値のあることである。なので驚くことに、圏論は性能のことは全く考えていないけれども、実践上の価値を持つ異なる実装を探索する機会をたっぷりもたらしてくれるのだ。

(和訳:@ashiato45

脚注
  1. 訳注: なので、モノイド全体を対象とし、その間の(集合の意味での)関数たちを射とする圏をモノイドの圏と思うことも一応できたがそうしなかった、という意味だと思われる。 ↩︎

  2. 訳注: 「直和をもとにした関手」ってなんだという感じがしますが、演習問題の6を解くとなんとなく分かる気がします。 ↩︎