圏論勉強会 第3回の自由対象で悲鳴が上がってたようなので、参考までに図に書いて説明しておく。
まず、マグマと自由マグマを以下のように定義する(というか、勉強会においてこう定義していた)。
class Magma a where magappend :: a -> a -> a data FreeMagma a = Leaf a | Node (FreeMagma a) (FreeMagma a) deriving Show instance Magma (FreeMagma a) where x `magappend` y = Node x y
このFreeMagmaが自由対象という性質を持つ事は、以下の図で捉えられる。
図の上半分はマグマと準同型がなす圏なので、登場するFreeMagma aとbはMagmaクラスのインスタンスであることが求められる。忘却関手というのは、上半分の圏からそのまま下半分の圏(HaskなんだけどSetsのつもり)に持ってくる事に該当する。また、自由対象であるためにはLeafという生成系aを自由対象FreeMagma aへ埋め込む射の存在も必要となる。
この状況でfを任意の関数として持ってきた時に、下の図を可換にするようなfoldMapMagma fという射が唯一存在するということが自由対象の性質となる。その唯一の射を得るためのfoldMapMagma関数は以下のように定義できる。ただし、これらの定義が本当に自由対象の性質を満たすのかは、きちんと証明する必要はある(もちろんそんな証明はこのエントリではしない)。foldMapMagma fは上の図の住人なので、これがマグマ準同型であることの証明も必要なのでお忘れなく。
foldMapMagma :: Magma b => (a -> b) -> FreeMagma a -> b foldMapMagma f (Leaf x) = f x foldMapMagma f (Node l r) = foldMapMagma f l `magappend` foldMapMagma f r
さて、自由対象が手に入ったのでその性質を利用してみよう。定義中のf :: a -> bは任意なのだから、好きな関数を用いることができる。ただし、bはMagmaクラスのインスタンスである必要がある。まずはbとして以下のようなKakkoという型を用意しよう。
newtype Kakko = Kakko String deriving Show instance Magma Kakko where Kakko x `magappend` Kakko y = Kakko ("(" ++ x ++ " " ++ y ++ ")")
KakkoはMagmaクラスのインスタンスとして定義しているので、bの要件を満たす。ここまでくればaとfはなんでもいい。面倒なのでKakko型のコンストラクタKakko :: String -> Kakkoをfとして使おう。すると、状況は以下の図のようになる。
かくして、foldMapMagma Kakkoという二分木に適用できる関数を手にする事ができた。これをNode (Leaf "Hello") (Leaf "World")という木に適用するというのが、勉強会中のデモでやっていたことだ。
勉強会ではモノイドも例として出していた。また適当なf :: a -> bを用意してみよう。bはMagmaクラスのインスタンスである必要があるが、モノイドがマグマであることからbとして任意のモノイドをとることができる。ただし、Haskellの場合はラップが必要なので以下のような型を定義しなければならない。
newtype WrappedMonoid a = WrappedMonoid a deriving Show instance Monoid a => Magma (WrappedMonoid a) where WrappedMonoid x `magappend` WrappedMonoid y = WrappedMonoid (mappend x y)
これで、WrappedMonoid (Sum Int)もWrappedMonoid (Product Int)もみんなMagmaクラスのインスタンスであり、型bとして用いる事ができるようになった。後は好きな型aに対してf :: a -> WrappedMonoid ...という関数を考えれば、二分木に適用できるfoldMapMagma fが手に入る。例えば、WrappedMonoid . Sum :: Int -> WrappedMonoid (Sum Int)などはfの例として使える。面倒だから図は載せないが、この例についても各自で先ほどと同様の図を書いてみると自由対象の感覚が掴めるようになるだろう。
