Login
Immutable PageDiscussionInfoAttachments
alstamber/CategoryTheoryAndHaskell

MMA

圏の概略

メタグラフ

次の2つを持つものをメタグラフという。

Category則

次の3つの規則を満たすメタグラフを圏と呼ぶ。
なお合成演算とは、射f : B -> C と 射g : A -> B について、射h : A -> Cを得るような演算である。

圏の例

Setはすべての集合をObjectとして持ち、射として関数、合成として関数合成を持つような圏である。

Grpはすべての群をObjectとして持ち、射として群演算を保存する関数(群準同型)を持つような圏である。
つまり、任意の2つの群G, Hについて、f(u*v) = f(u) . f(v)であることと、f : G -> H はGrpの射であることは同値である。

Hask圏

圏の考え方をHaskellに拡張するために、Hask圏というものを定義する。これは

Hask圏がCategory則を満たしているかどうかは容易に確認できる。ただ注意するべきなのは、恒等射である。
Haskellにおける恒等射はid関数だが、このid関数は多相的である。つまり、定義域や値域として異なる型を取ることができる。
一方で、圏論における恒等射はSource ObjectとTarget Objectを指定して定義する。もっとも、Haskellにおける多相関数は型を明示することで単相にできるので、この違いはそれほど大きな問題を産まない。

Functor

Functorは圏同士の対応を表すものである。圏CとDが与えられた時、Functor F : C -> D は次のような役割を果たす。

Functorにも従わなければならないルールであるFunctor則が存在する。

HaskellにおけるFunctor

Haskellの型クラスであるFunctorは、圏論のFunctorの概念を取り入れたものである。HaskellのFunctorはHask圏からfuncへのFunctorになっている。
funcとはFunctorの型の上でちょうど定義されるHask圏の部分圏である。例えばListのFunctorはHask圏からLst圏へのFunctorである。
Lst圏はリスト型のみを含むような圏である。Lst圏における射はリスト型の上で定義される関数のことであり、すなわち任意の型T, Uについて[T] -> [U]であるような関数である。

Maybeを例にこの事を考えてみる。

   1 instance Functor Maybe where
   2     fmap f (Just x) = Just (f x)
   3     fmap _ Nothing = Nothing

Maybeは型コンストラクタであり、任意の型Tをとって型Maybe Tとなる。また、fmapはMaybe型のみを対象とするようになり、関数(a -> b)をとって、関数(Maybe a -> Maybe b)を返す。つまり、Hask圏のObjectである任意の型Tをとって、別の圏(Maybe型がObjectで、Maybe型上の関数が射となっている)のObjectを返すなにかと、Hask圏の射をとって、この新しい圏の射を返すなにかを定義したのである。つまりMaybeはFunctorである。

自然変換

Monad

alstamber/CategoryTheoryAndHaskell (last edited 2014-04-22 23:41:41 by alstamber)