Category of algebras

学習/備忘 Haskell/Category theory

自然数の集合Nに対して、関数f x = x * nを定義すれば、{N,f}は圏であることは明らかだろう：

objects: n
morphisms: f: n -> n'
id: f x = x * 1

そこで、fはもう一つの圏のmorphismsとして働くことができる、Haskellの例：

foo :: (Int -> Int) -> (Int -> Int -> Int) -> Int -> Int -> Int
foo f g x y = g (f x) (f y)

add = foo f (+) where f = (*2)

ここで、「f x = x * 2」がバイナリ演算子の「+」を同じくバイナリ演算子の「add」へマッピングした：

f: + -> add

勿論compositionとidのルールも成立する：

-- add2 == add3

add2 = foo ((h . g) . f) (+)
         where f = (*2)
               g = (*3)
               h = (*4)

add3 = foo (h . (g . f)) (+)
         where f = (*2)
               g = (*3)
               h = (*4)

id = (*1)

ということで、ひとつの圏が出来上がり：

objects: +
morphisms: f: + -> +'
id: f x = x * 1

このような圏をAlg(II)と呼ぶらしい。さらに特殊な情況、（上記の例のような）「+」はmonoidの場合、圏をMonと呼ぶ。MonはAlg(II)のsubcategory。