５ 随伴とデータベース
これまで、圏論の理論的な面を重視しながら、重要な定理である随伴まで学んできた。これだけ学んだのだから素晴らしい応用に出会えるはずだ、と考えるのは当然のことだ。ここでは、情報技術の中でも特に重要なデータベースとの関連について、説明しよう。
５．１ Lensの説明
Haskellには、データベースのために、Lensと呼ばれるパッケージが用意されている。それでは、これをインストールしよう。Windows 10であればコマンドプロンプトを、linuxであれば端末(terminal)をひらいて、次のようにすればよい(Haskellがインストールされていることが前提になっているので、まだの場合にはHaskellを利用できるようにしてからだ)。
cabal install lens
それでは使ってみよう。データベースは、あることに関する情報を、テーブル(表)という形式で表したものだ。例えば、あるクラスの生徒の期末試験の成績を一覧表で示したものは、立派なデータベースだ。成績の一覧表には、縦方向に生徒名が記されているであろう。横方向には、生徒名、学籍番号、各科目での得点、合計点などが書き込まれているであろう。各生徒に対する情報、すなわち横一行の情報はレコードと呼ばれる。そして、レコードに刻まれた一つ一つの情報、生徒名、学籍番号、それぞれの科目の得点、合計点は、フィールドと呼ばれる。
ここでは車に関するデータベースを考え、レコードには、メーカーと形式が書き込まれていることとし、型式は車種名と製造年から成り立っているとしよう。
最初に、\(Lens\)のモジュールをロードし、\(car\)と名付けたレコードを用意しよう。このレコードでは、メーカーはホンダ、車種はアコードで２０１２年製であったとする。
{-# LANGUAGE TemplateHaskell #-} import Control.Lens car = ("Honda", ("Accord", 2012))
とすればよい。
\(Lens\)は虫眼鏡を意図して付けられた言葉だと思うが、\(car\)のフィールドを覗くために、\(view\)という関数が用意されている。例えばメーカー名は知りたいとしよう。これは最初のフィールドなので、
view _1 car
とすればよい。
また、形式は２番目のフィールドなので
view _2 car
とすればよい。
さらに、車種名を知りたいときは、２番目のフィールドの最初のデータなので、
view _1 $ view _2 car
とすればよい。
Haskellには、\(view\)に似ているが、\(getter\)と呼ばれる別の関数が用意されていて、\( ( \verb|^|.) \)で表される(これは中置関数にするとカッコが外れて\( \verb|^.| \)となる)。\(n\)番目のフィールドを取り出す時は、\( \verb|^| .n\)とする。さらに得られたフィールドの\(m\)番目のデータを取り出すためときは\( \verb|^| .n.m\)となる。
先ほどの\(view\)での操作と同じことを\( ( \verb|^|.) \)で行うと次のようになる。
car^._1 car^._2 car^._2._1
この記述はオブジェクト指向言語での記述と一緒なので、この言語に慣れている場合には、分かりやすいだろう( \(getter\)の関数の定義でピリオドを用いて、あたかも関数の合成のように見せかけているのは、ずるがしこいとも思えるが)。
フィールドを書き換えて新しいレコードを得るためには、\(set\)を用いる。この関数は3個のパラメータを有する。最初のパラメータはフィールドの場所、２番目のパラメータは書き換える内容、３番目のパラメータはレコードだ。ホンダをトヨタに書き換えたレコードを得るためには、
car1 = set _1 "Toyota" car
とすればよい。新しいレコードを\(car1\)に設定し直していることに注意して欲しい。もちろん古いレコード\(car\)はそのままだ。さらに、車種をアクアに変更するには、
car2 = set (_2._1) "Aqua" car1
\(set\)に対しては、\(setter\)と呼ばれる別の関数が用意されており、これは\( ( \verb|~|. )\)である(これも中置関数にすると\( \verb|~|.\)となる)。使い方は同じで、次のようになる。
car1 = (.~) _1 "Toyota" car car2 = (.~) (_2._1) "Aqua" car1
中置関数にすると、
car1 = _1.~ "Toyota" $ car car2 = (_2._1) .~ "Aqua" $ car1
\( ( \_2.\_1) .\verb|~| "Aqua" \)の部分が関数なので、\( \&\)を用いて、関数と変数の順序を入れ替えると、
car2 = car1 & (_2._1) .~ “Aqua”
通常はこのように記述するのがふつうである。これもオブジェクト指向と同じ記述になり、読みやすい。
同じことの繰り返しになるが、実行例を示しておこう。
{-# LANGUAGE TemplateHaskell #-} import Control.Lens data Car = Car {_maker :: String , _spec :: Spec} deriving Show data Spec = Spec {_name :: String, _year :: Int} deriving Show makeLenses ''Car makeLenses ''Spec
今までの説明では、フィールドは何番目にあるかで示していたが、ここでは、フィールドはキーで呼ばれる。キーはフィールドに割り振られた名前の\(maker\),\(spec\),\(name\),\(year\)だ。実行例に示すように、合成関数でキーを連ねることで、ターゲットとするデータにアクセスできる。これは重要な点である。すなわちオブジェクト指向のときと全く同じ操作でたどり着くことができる。なぜ可能なのかについては後半で説明する。
パッケージのLensにはいくつかの例が用意されているので、興味がある場合には利用するとよい。例えば、\(Turtle\)は、亀が指示により位置、色、進行方向を変える単純な遊びだ(追加パッケージとしてStreams,glossを必要とする)。また\(Pong\)は球をパドルで撃ち合う単純なゲームだ(追加パッケージとしてdefault-data-classを必要とする)。これらから、データベースとアニメーションの関係がどのようになっているかを知ることができ、面白いことと思う。
５．２ F-余代数でデータベースを定義する
\(getter\)と\(setter\)の型シグネチャを求めてみよう。
\(getter\)の\( ( \verb|^|.) \)では、\(s\)はレコードで、最初の\(a\)はデータを取り出すフィールドで、最後の\(a\)は取り出したデータだ。\(Getting \ a \ s \ a\)は指定されたフィールドからデータを取り出すための関手(あるいは関数)だ。
\(setter\)の\( (. \verb|~|) \)では、\(s\)は入力のレコード、\(t\)は出力のレコード、\(a\)はフィールドで、\(b\)はそのフィールドに書き込む入力値だ。\(ASetter \ s \ t \ a \ b \)は指定されたフィールドを修正した新たなレコードを得るための関手(あるいは関数)だ。
Haskellの関数を簡略化し、ここではアクセスするフィールドの場所が関数の名前の中に含まれる\(getter\)と\(setter\)を、用意することにしよう。そうすると、先ほどの型シグネチャの中の\(Getting \ a \ s \ a\)と\(ASetter \ s \ t \ a \ b \)とが省かれることになるので、次のようになる。
get :: s -> a set :: s -> b -> t
例を挙げることにしよう。今、2つの要素からなる簡単なレコードがあったとしよう。第1、第2番目のフィールドにアクセスする\(getter\)と\(setter\)は、例えば、次のように実現できる。
get_1 :: (a,b) -> a get_1 (x,y) = x set_1 :: (a,b) -> c -> (c,b) set_1 (x,y) z = (z,y) get_2 :: (a,b) -> b get_2 (x,y) = y set_2 :: (a,b) -> c -> (a,c) set_2 (x,y) z = (x,z)
Lensにでは、\(setter\)と\(getter\)の合成関数が満たさなければならない条件を定めている。３個の条件があり、これをLensの３法則と呼ぶことにしよう。我々が定めた\( (set \_1,get \_1) \)の組に対して３法則を定めると以下のようになる( \( (set \_2,get \_2) \)の組に対しても同じ)。詳しくはパッケージLens参照。
set_1 s (get_1 s) = s get_1 (set_1 s a) = a set_1 (set_1 s a) b = set_1 s b
\(setter\)と\(getter\)の型シグネチャをまとめると、\(s \rightarrow (a, b \rightarrow t) \)になる。
ここまではHaskellでの記述であったが、圏論での記述に代えてみよう。ここでは話を簡単にするために、\(a\)と\(b\)は同じデータ型であるとし\(a\)で表すことにする。同様に、\(s\)と\(t\)も同じだとし、\(s\)で表すことにする。従って、\(s \rightarrow (a, b \rightarrow t) \)の代わりに\(s \rightarrow (a, a \rightarrow s) \)で考えることとする。
Haskellでの型変数\(s,a\)は、圏論での対象\(S,A\)として記述できる。これより、Haskellでの\(s \rightarrow (a, a \rightarrow s) \)は、圏論では\( \forall S \rightarrow (A, A \rightarrow S) \)となる。そして、\(S,A\)は圏\( \mathcal{C}\)の対象としよう。ここで射の合成が保存されるならば、自己関手\(F\)が存在する。
いま自己関手\(F\)が存在するものとしよう。関手\(F\)は、\(S\)を\(A \cup (S \times A) \)に写していると考えることができる(下図)。
これから\(α:S \rightarrow A \cup S \times A=F (S) \)となり、F-余代数\( (S,α)\)が得られる。
それではこのF-余代数をHaskellで実現することを考えよう。
まず代数的データ型を定義しよう。
data Store a s = Store a (a -> s)
それではいま定義した代数型データ型\(Store \ a \ s\)を、ファンクタにしよう。\(s\)が\(Store \ a \ s\)となるので、ファンクタは\(Store \ a\)となる。またファンクとするためには射の合成が保存されるように\(fmap\)を定義する必要がある。これは以下のようになる。
instance Functor (Store a) where fmap g (Store a f) = Store a (g . f)
図で表すと以下のようになる。
しかしこの図だけからは何とも分かりにくい。そこで、汎用性を失わないようにしながら、議論が平易に進められるようにするために、データベースは、二つのフィールド\(a,b\)からなる単純なものとし、これを\(s=(a,b)\)としよう(ここでは先ほど設けた制限を緩めて\(a\)と\(b\)の対象(データ型)は異なってもいいものとする)。そしてこれへの操作も最初のフィールドにアクセスする関数\(get \_1,set \_1\)だけとしよう。
このようにすると、上の図は次のように表すことができる。
この図で、操作を施そうとしているレコードは\( (a,b)\)である。ここでは最初のフィールドに対して操作が施される。\(get \_1\)であれば、\(a\)が読みだされる。また、任意の\(x \in A\)が\(set \_1\)によって書き込まれると、新しい内容は\( (x,b)\)となる。図では任意の\(x\)なので、新しい状態を\( ( \_,b) \)とした。
データベースでのこのような操作(図の左側)を、関手(ここではファンクタ\(Store\ a\))で写したのが図の右側である。\(Store \ a \ ( λx \rightarrow (x,b))\)のうち\(a\)は\(get \_1\)の操作を\( ( λx \rightarrow (x,b))\)では\(set \_1\)の操作を表している。これを青色の小文字\( get \_1,set \_1 \)を明示した。カリー化を利用して、\(get \_1 : S \rightarrow A, get \_1 : S \rightarrow A \rightarrow S \)であることに注意して欲しい。
今までの説明は、\(set \_1\)を一回だけ施したものであったが、何回も繰り返した場合はどうなるだろうか。図で示すように\( (x,b)\)を\(Store \ x ( λy \rightarrow (y,b)) \)で置き換えればよい。同じように\( (y,b) \)を置き換えれば、\(set \_1\)を繰り返したときにファンクタ\(Store \ a\)に写された側を得ることができる。ここでもまた青色の小文字\( get \_1,set \_1 \)で明示し、写像された空間での操作が実際どのように表現されるかを明らかにした。
ここから分かることは、データベースへの繰り返しの操作は、これらに対する関数の合成として表されるということであり、オブジェクト指向的に表されるということである。このことについては、このあとより数学的に厳密に説明する。
代数的データ型で表されたファンクタはF-代数で表すことができた。もし、\(F(A) \rightarrow A\)であるならば、F-代数で表すことができる。しかしここでは\(A \rightarrow F(A) \)となっていて、矢印が反対向きだ。でもひるむことはない。双対関係にあるF-余代数を用いればよい。それは次のようになる。
type Coalgebra f a = a -> f a coalge :: Coalgebra (Store a) (a,b) coalge (a,b) = Store (get_1 (a,b)) (set_1 (a,b))
５．３ コモナドでデータベースを定義する
それでは\(Store \ a\)を\(Comonad\)のインスタンスにしてみよう。コモナドは\(extract: W (A) \rightarrow A\)と\(duplicate：W (A) \rightarrow W (W (A)) \)を用意しなければならない。そこで、次のようにしよう。
class (Functor w) => Comonad w where extract :: w s -> s duplicate :: w s -> w (w s) instance Comonad (Store a) where extract (Store a f) = f a duplicate (Store a f) = Store a ( \q -> Store q f)
少し使ってみよう。
上図では次のことを行っている。現在のレコードの内容を\( (a,b)\)とする。このレコードへのアクセス( \(setter, getter\)による )を、ファンクタ\(Store \ a \)で写した空間で\(Store \ a \ ( λx \rightarrow (x,b))\)と表すことができる。これに\(extract\)を施すと、元の状態の\( (a,b)\)を得る。
\( (a,b)\)に対する２度の繰り返しのアクセスを、\(Store \ a \)に写像した空間では、\(duplicate \ Store \ a \ ( λx \rightarrow (x,b))\)となる。もちろんこれに\(extract\)を２回施すと、元の状態の\( (a,b)\)を得る。
ここまでの議論から、ファンクタ\(Store \ a\)から作られた余代数\(coalg\)は、コモナドの特殊な例であることが分かる。そして、下図の可換図式が成り立つとき、\(coalg\)はコモナド余代数(comonad coalgebra)と呼ばれる。
可換図式をHaskellで表すと次のようになる。
extract.coalg = id fmap (coalg) . coalg = duplicate . coalg
それではこの可換図式を用いて、\(Lens\)の３法則
set_1 s (get_1 s) = s get_1 (set_1 s a) = a set_1 (set_1 s a) b = set_1 s b
が成り立っていることを示そう。
最初の式より、
(extract.coalg) s = s
を得る。
左辺を展開すると、
(extract . coalg) s) = extract (Store (get_1 s) (set_1 s)) = set_1 s (get_1 s)
となる。これが右辺と等しくなるので、
set_1 s (get_1 s) = s
これで、３法則の最初が満たされていることが分かった。
２番目の式より
(fmap (\s’ -> coalg s’) . coalg) s = (duplicate . coalg) s
左辺を展開すると、
(fmap (\s’ -> coalg s’) . coalg) s = fmap (\s’ -> Store (get_1 s’) (set_1 s’)) Store (get_1 s) (set_1 s) = Store (get_1 s) ( (\s’ -> Store (get_1 s’) (set_1 s’)) . (set_1 s))
右辺を展開すると、
duplicate . coalg s = Store (get_1 s) (\y -> Store y (set_1 s))
これより
((\s’ -> Store (get_1 s’) (set_1 s’)) . (set_1 s))
と
\y -> Store y (set_1 s)
が等しくなる。
そこで、\(y\)は任意の値に対して有効であるので、\(a1\)という値が入力されたとしよう。右辺の式は
((\s' -> Store (get_1 s’) (set_1 s’)) . (set_1 s)) a1 = (\s' -> Store (get_1 s’) (set_1 s’)) (set_1 s a) = Store (get_1 (set_1 s a1)) (set_1 (set_1 s a1))
となり、左辺は
(\y -> Store y (set_1 s)) a1 = Store a1 (set_1 s)
となる。これより、それぞれの\(Store\)の項目同士が等しいことから
get_1 (set_1 s a1) = a1 set_1 (set_1 s a1) = set_1 s
が得られる。
これにより、\( (get \_1,set \_1)\)に対して、\(Lens\)の３法則が成り立っていることが示すことができた。ここでは\( (get \_1,set \_1)\)に限定して行ったが、汎用な\(getter,setter\)に対しても成り立つ。これについては次の記事で説明する。
