bitterharvest’s diary

A Bitter Harvestは小説の題名。作者は豪州のPeter Yeldham。苦闘の末に勝ちえた偏見からの解放は命との引換になったという悲しい物語

表現可能関手

5. 表現可能関手

日本の歴史を学んでいるといくつもの学説に出会う。それらの中で、圏論との関わりが面白いと思った学説が中世史にあったので、それを最初に紹介しよう。

一つは、「権門体制論」である。黒田俊雄氏の学説で、中世の国家体制は、公家権門(執政)、宗教権門(護持)、武家権門(守護)の三つの権威から成り立っていて、それらは相互補完的な関係にあると主張されているものである。

また、佐藤進一氏は、室町時代初期の統治体制を「将軍権力の二元論」だと言っている。これは将軍権力が主従的支配権と統治的支配権に分割され、運用されているという学説で、主従的支配権はいわゆる「御恩と奉公」を基盤とした軍事、統治的支配権は「建武式目」をベースとした法による統治である。

二つの学説に対しては賛否両論があるようだが、歴史認識から離れて、数学の圏論という立場からは、構成要素を重視している「権門体制論」は「対象」という視点から、支配者と被支配者との関係に重みを置いている「将軍権力の二元論」は「射」から中世史を考察しているように見える。物事を分析するとき、対象を中心にしてみる見方と射を中心にしてみる見方の二つがあることは面白いことだと思う。

さらに、圏論に深くかかわっていると、圏の構造を表現している射の方が大切に見える。この立場から言うと、黒田氏よりも佐藤氏の見方に同調できる部分が多いのだが、どうだろうか。

そのような議論を打ち消してくれるのが、今回の表現可能関手(representable functor)だ。対象と射の間は行ったり来たりできますよと説明してくれる。

今回の話を分かりやすくするために、別の話題を挙げておこう。今日では、電卓を使えば、三角関数や常用対数の値を簡単に求めることができるが、このような道具がなかった時代には、数表が便利な道具であった(下図)。アマゾンで調べてみると、1981年には、まだ、吉田洋一・吉田正夫著『数表(新数学シリーズ)』が出版されている。おそらく、このころからそんなに離れていない時代に、書籍としては出版されなくなったのであろう。しかし、電卓が発明されていない時代には、重宝した。
f:id:bitterharvest:20180216123738j:plain

この数表が表現可能関手だ。数表は関数をテーブルという形式で表してくれる。関数の方はもちろん圏論での射である。テーブルはデータだ。圏論での対象に当たる。従って、数表は、射を対象で表したものだとは思えないだろうか。表現可能関手は、このような関係を圏論の言葉で厳密に定義したものである。そう思うと、なあんだということになるけれども、「数表」を数学的な概念に変えた意義は大きいと思う。

5.1 自然変換

圏論の中で自然変換は大切な概念である。関手から関手への関数が自然変換である。関手は、ある圏の構造を別の圏に、その構造を維持したまま移動させてくれる。そして、圏を対象とし、関手を射とすることで、抽象化された新たな圏を構成できる。これは「圏の圏」と呼ばれる。そして、二つの圏の間で関手を考えたように、二つの「圏の圏」の間で関手、この場合には自然変換と呼ばれるが、を結ぶことで、さらに抽象化が可能となる。そして、素晴らしいことに、自然変換によっても元々の圏の構造は維持される。

従って、圏論では、関手と自然変換によって抽象化を進めることができるが、その抽象化はもともと持っていた圏の構造を維持するという貴重な性質を有している。

そこで、ここではもう一度、自然変換について復習しておこう(下図)。
f:id:bitterharvest:20180215212310p:plain

今、圏\(\mathcal{C}\)が存在したとしよう。\(\mathcal{C}\)を圏\(\mathcal{D}\)に関手\(F,G\)で写したとしよう。一般に、関手によって写された空間はシート(sheet)と呼ばれる。図では、\(F\)によって写された部分を\(Sheet \ A\)とし、\(G\)による部分を\(Sheet \ B\)とした。玉ねぎは鱗片葉と呼ばれる厚肉の皮が層をなしているが、玉ねぎを圏と考えて鱗片葉をシートとすれば、イメージしやすいと思う。

自然変換はシート間で写像を結んだ時、それらが可換になるというものだ。これだけでは曖昧なのでもう少し厳密に定義することとしよう。今、\(\mathcal{C}\)の任意の対象を\(X\)としよう。そして、\(X\)をソースとしている任意の射を\(f\)とし、そのターゲットを\(Y\)としよう。即ち、\(f : X \rightarrow Y\)としよう。ここで、\(X,f\)は任意であることに注意してほしい。

自然変換は、要素ごとに可換になっていることである。そこで、\(X\)について考える。この時、\(Sheet \ B\)から\(Sheet \ A\)への射\(\alpha\)を考えることとする。これが自然変換となるためには、対象\(X\)によって作られた四角形、この場合には\(F(X),F(Y), G(X),G(Y)\)が可換である、即ち、\(F(f) \circ \alpha_X\)と\(\alpha_Y \circ G(f) \)が同値である。

即ち、\(F\)と\(G\)の間に自然変換が存在するための必要十分条件は、任意の\(X,f:X \rightarrow Y\)に対して
\begin{eqnarray}
F(f) \circ \alpha_X = \alpha_Y \circ G(f)
\end{eqnarray}
が成り立つことである。

なお、\(Sheet \ A\)から\(Sheet \ B\)への射\(\beta\)についても同様である。

5.2 \(\rm{Hom}\)関手

それでは、射を対象として扱えるようにしよう。それは次のように行う。対象を一つ定める。そして、この対象から出ている射を利用して、それにつながる対象を覗けるようにするというのが趣旨だ。具体的には、対象の一つを\(A\)としよう。そして、任意の対象を\(X\)としよう。これらの対象間の射の集合を\(\mathcal{C}(A,X)\)とする。ここで、\(\mathcal{C}\)はこれら対象が属している圏である。射の集合は\(\rm{Hom}\)集合とも呼ばれる。以後ではこの言葉を用いることとする。

\(\mathcal{C}(A,X)\)が属す圏を集合の圏となるので\(\mathcal{Set}\)と表すことにしよう。この圏では\(\mathcal{C}(A,X)\)が対象となる。即ち、\(\mathcal{C}\)では射と見なしていたものが、圏\(\mathcal{Set}\)では対象として使われる。抽象化のレベルが一つ上がったと考えてよい。\(X\)が任意であることから、圏\(\mathcal{C}\)から圏\(\mathcal{Set}\)への関手が存在する。これを\(\mathcal{C}(A,-)\)と記述し、\(\rm{Hom}\)関手と呼ぶこととする。
f:id:bitterharvest:20180318080938p:plain

上記の説明では\(A\)から出ていく射の集合を考えた。もちろん、下図のように\(A\)へ入ってくる射の集合も考えることができる。前者は共変関手、後者は反変関手と呼ばれる。双対の関係にあるが、ここでは共変関手を用いて、表現可能関手を説明する。反変関手の場合はどのようになるかは、別途、考えて欲しい。
f:id:bitterharvest:20180318095940p:plain

5.3 表現可能関手

上の説明で、関手\(\mathcal{C}(A,-)\)を用いて、圏\(\mathcal{C}\)から圏\(\mathcal{Set}\)に写した。しかし、下図に示すように別の関手\(F\)も写せる場合がある。このような場合、任意の\(X\)に対して、関手\(\mathcal{C}(A,-)\)と関手\(F\)の間で自然変換を考えることが可能になる。

このような時、自然変換\(\alpha : \mathcal{C}(A,-) \rightarrow F\)と\(\beta : F \rightarrow \mathcal{C}(A,-) \)が存在し、\(\alpha \circ \beta = id\)かつ\(\beta \circ \alpha = id\)が成り立つとき、関手\(F\)を表現可能関手と呼ぶことにする。なお、\(\alpha \circ \beta = id\)かつ\(\beta \circ \alpha = id\)が成り立つとき、自然同型(natural isomorphism)であるという。
f:id:bitterharvest:20180318081114p:plain



これは、関数と関数値(の列)が一対一に対応していることを意味している。

5.4 Haskellへの準備

それでは、Haskellでプログラムを書けるようにするための準備をしよう。

\(X\)からの任意の射を\(f\)とし、\(f:X \rightarrow Y\)とした時、下図のように可換図を得る。
f:id:bitterharvest:20180318081727p:plain

上の図から次のことが言える。任意の\(X\)に対して、\(\mathcal{C}(A,X) \rightarrow F(X)\)であることから、
\begin{eqnarray}
\alpha_X : (A \rightarrow X) \rightarrow F(X)
\end{eqnarray}
逆に、\( F(X) \rightarrow \mathcal{C}(A,X)\)であることから、
\begin{eqnarray}
\beta_X : F(X) \rightarrow A \rightarrow X
\end{eqnarray}
と言える。なお、上の式では\((A \rightarrow X)\)とせず、カーリー化して\(A \rightarrow X\)とした。

そして、自然同型であるためには、次の条件を満たす必要がある。
\begin{eqnarray}
\alpha_X \circ \beta_X = id \\
\beta_X \circ \alpha_X = id
\end{eqnarray}

冒頭で、表現可能関手は数表だといった。例えば、角度に対してその正弦を与える関数\(sin’\)の数表は次のようになる。
f:id:bitterharvest:20180215212928p:plain

上の図から\(\alpha\)は次のようになっていることが分かる。
\begin{eqnarray}
\alpha : (Integer \rightarrow Double) \rightarrow [Double]
\end{eqnarray}
また、\(\beta\)は次のようになる。
\begin{eqnarray}
\beta : [Double] \rightarrow Integer \rightarrow Double
\end{eqnarray}

5.5 Haskellで表現可能関手を使う

これらの知見を得て、表現可能関手をHaskellで実現しよう。まず、表現可能関手は複数の異なるデータが有する共通的な性質なので、クラスとして定義しよう。ここでは\(Representable\)と呼ばれるクラスを用意しよう。表現可能関手は今までの説明では\(F\)を用いてきたので、ここでは小文字にして次のように定義しよう。

class Representable f where

次に、このクラスで用いられる演算を定義する必要がある。それは次のものである。
\begin{eqnarray}
\alpha & :& (A \rightarrow X) \rightarrow F(X) \\
\beta &:& F(X) \rightarrow A \rightarrow X
\end{eqnarray}

しかし、この演算では\(A\)という対象を必要としている。このため、これをデータ型として定義する必要がある。Haskellでは対象はデータ型として定義される。データ型は\(type\)を用いて定義できる。
そこで、\(A\)を型コンストラクタとしその型は表現可能関手\(F\)とする。但しプログラムでは小文字の\(f\)を用いて

class Representable f where
  type A f :: *

とすればよい。ここで、\(*\)は単にタイプであることを意味する。しかし、これでは\(A\)の意味がはっきりしないので、表現可能であるということをはっきりさせるために、\(A\)の代わりに\(Rep\)を用いて次のように定義しよう。

class Representable f where
  type Rep f :: *

次に\(\alpha\)の機能は表を作ることなので、その意味を持たせて\(\alpha\)を\(tabulate\)とし\(\beta\)は表から索引してくると解釈できるので、\(\beta\)を\(index\)として、関数を実現すると次のようになる。

なお、{-# LANGUAGE TypeFamilies #-}が必要である。

{-# LANGUAGE TypeFamilies #-}
class Representable f where
  type Rep f :: *
  tabulate :: (Rep f -> x) -> f x
  index :: f x -> Rep f -> x

圏論では、自然同型となるためには、
\begin{eqnarray}
\alpha \circ \beta = id \\
\beta \circ \alpha = id
\end{eqnarray}
を満たす必要であった。しかし、Haskellはデータ型を変数として利用するため、上の条件は常に満たされる。従って、自然変換の条件が満たされているかどうかに注意を払う必要はないという便利な面をHaskellは有している。

\(tabulate\)と\(index\)の意味については上述したが、重要なので、もう一度説明をし直しておこう。上のプログラムで、\(tabulate\)は表を作る関数である。これに対して、\(index\)は次のように理解できる。\(f \ x\)で表を得る。\(Rep \ f \)で表を索引するためのキーを与える。このため、しばしば\(Rep\)に変わって\(Key\)という名前を使っている例も見かける。そして、このキーで索引して得られるのが値\(x\)である。

それでは、このクラスを利用してみよう。表現可能関手としてリストを用いてみよう。ただし、このリストは空リストを含まないものとする。そこで、次のデータ型\(Stream\)を用意しよう。

data Stream a = Cons a (Stream a)

これを用いて、クラス\(Representable\)のインスタンスを用意しよう。次のようになる。

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

\(Rep \ Stream\)のデータ型は\(Integer\)としよう。ただし、0より大きい整数とする。上記で少し述べたが、ここでは\(Rep\)よりは\(Key\)のほうが分かりやすいと思う。リスト(\(Stream\))への索引に用いているキー(\(Key\))のデータ型は\(Integer\)であると考えたほうが素直である。

次に関数の部分を説明しよう。\(tabulate\)は\(Stream\)、即ち、表(リスト)を作成する。表の中に入るのは、\(f : A \rightarrow X\)とした時、\(f(A)\)である。そこで、\(f\)を引数にして、表を作成できるようにする。即ち、\(tabulate\)は関数\(f\)に対して、\([ f(0), f(1),f(2),…]\)の表を作成する。

\(index\)は、表の\(n\)番目に入っている値を取り出す。

それでは、この表現可能関手を用いてみよう。

最初の例は、\(y= 2 \times x\)の数表を求めるものである。

a = tabulate (*2) :: Stream Integer

この数表は、\(n\)番目の場所に\(2 \times n\)の値が入っている。それでは、5番目のところを求めて見よう。

Prelude> :load "Representable.hs"
[1 of 1] Compiling Main             ( Representable.hs, interpreted )
Ok, modules loaded: Main.
*Main> a = tabulate (*2) :: Stream Integer
*Main> index a 5
10

それでは、\(n\)番目の場所に\(a\)という文字が\(n\)個は言っている数表の例を考えてみよう。数表は次のようになる。

*Main> toLetter n = if n==0 then "" else "a" ++ toLetter (n-1); b = tabulate toLetter :: Stream String

やはり、5番目の値を求めて見よう。

*Main> index b 5
"aaaaa"

最後に、角度からその正弦を求める関数\(sin'\)の数表を考えよう。\(n\)番目には、\(n\)度に対する制限が入っていることにする。数表は次のようになる。

*Main> sin' :: Integer -> Double; sin' x = sin $ (fromIntegral x) * pi / 180; c = tabulate sin' :: Stream Double

それでは5度の時の正弦を求めて見よう。

*Main> index c 5
8.715574274765817e-2

上記のプログラムを図で示すと下図のようになる。
f:id:bitterharvest:20180318081252p:plain

プログラムの全体を示しておこう。

{-# LANGUAGE TypeFamilies #-}

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

data Stream a = Cons a (Stream a)

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

a = tabulate (*2) :: Stream Integer
--index a 5

toLetter n = if n==0 then "" else "a" ++ toLetter (n-1)
b = tabulate toLetter :: Stream String
--index b 5

sin' :: Integer -> Double
sin' x = sin $ (fromIntegral x) * pi / 180
c = tabulate sin' :: Stream Double
--index c 5