圏の概略

メタグラフ

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

• Objectの集まり
• ふたつのObject(Source ObjectとTarget Object)を一つに結びつける射の集まり

  • fがAからBへの射であるとき、f : A -> B とかく

Category則

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

• 射の合成は結合的でなければならない
  • f ○ (g ○ h) = (f ○ g) ○ h
• 圏は合成演算において閉じていなければならない

  • f : B -> C かつ g : A -> B ならば、h = f ○ g のような射h : A -> C がその圏に存在しなければならない

• 任意のObjectについて恒等射が存在しなければならない

  • 任意の射g : A -> B について、g ○ idA = idB ○ g = g となるようなidA, idBが存在しなければならない

圏の例

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

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

Hask圏

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

• Haskellの型をObjectとする
• Haskellの関数を射とする
• 合成として関数合成(.)をとる

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

Haskellにおける射の合成

Functor

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

• C内のあらゆるObject AをD内のF(A)に対応づける

• C内の射 f : A -> B を D内のF(f) : F(A) -> F(B)に対応づける

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

• 任意のObject A上の恒等射idAについて、F(idA)も恒等射でなければならない
• Functorは射の合成を分配しなければならない
  • F(f ○ g) = F(f) ○ F(g)

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