Haskellと圏論、再々度 - ryamadaのコンピュータ・数学メモ

こちらでHaskellと圏論についてメモした
随分、昔
少し、Haskellの知識が増えたので、何度目かの整理『Haskellと圏論』
基本資料はこのWikibooks
圏の基礎
- 「対象となる何かA『ソースオブジェクト』」→(AからBへと対応付けるものf『射』)→「対象となる何かB『ターゲットオブジェクト』という三つ組が作り上げる世界が圏
  - $f : A \to B$ がオブジェクトA,Bとfとの関係の表記
  - 圏には、{A,B,C,...}と{f1,f2,...}とがあって「世界」を作る
  - 圏を構成するオブジェクトと圏を構成する射とが満足するべき規則
    - 圏の射は合成的でる(そして、モノイド的(合成的演算が定義されていて単位元がある代数構造)である)
      - $f:A\to B$ と $g:B \to C$ が存在するならば、 $h:A \to C$ が存在する
        
        言い換えると、合成である射 $h = g \circ f$ が存在し、それが結合的
      - 恒等射 $id_A : A \to A$ がすべてのオブジェクトに存在する
- 半順序という圏について考えることで射、射の合成について整理する
  - 半順序があって、A<=B<=C<=D,A<=E<=Dとなっているとき、順序が定義できるオブジェクトペアすべてに射を作ると、A->B,A->C,A->D,A->E,B->C,B->D,E->Dが作られることになる。これをよく見れば、すべての合成射が作られている(各オブジェクトに恒等射も作る)。これが半順序の圏
Haskellの中にあるHaskという圏(こちらを参照)
- オブジェクトはデータ型
- 射は関数
  - 関数の合成は $f.g$ のように実行できる
  - 恒等関数を用意してある
圏から圏論へ
- 圏ができてうれしいわけだけれど、圏論は、「圏を扱う数学」だから、もっとできる
- 圏Ｃと圏Ｄがあったときに、圏Ｃを圏Ｄに対応付けるのが「関手 Functor」
- 関手 Functorは圏Ｃの $f_C:A_C \to B_C$ を $g_D:X_D\to Y_D$ に対応付ける( $A_C => X_D,B_C => Y_D,f_C => g_D$ とそれぞれ対応づいている)
- この関手 Functorにも恒等関手があってモノイド的
- 関手が満たすべき性質
  - 恒等射は関手によって恒等射に写される( $F(id_{(A)}) = id_{(F(A)}$ )
  - 射の合成構造も関手によって維持される( $F(f\circ g)=F(f) \circ F(g)$ )
- 以下のHaskellのFunctorの定義で言えば、a,bは圏Ｃのソースオブジェクトとターゲットオブジェクトであり、(a -> b)である関数がある。 $f_{a\to b} : a \to b$ の $f_{a\to b}$ が書かれていないだけ。そこにFunctor fを掛けると、 $g_{x \to y} : x \to y$ という関数gとソースオブジェクトx、ターゲットオブジェクトyと言うような、圏Ｄにおける関数gが作られる、というように書かれている

class Functor (f :: * -> *) where
  fmap :: (a -> b) -> (f a -> f b)

Haskellの圏はHaskだけではない
- 上記では、Haskellが圏論で説明できることを、Haskと呼ばれる「データ型をオブジェクトとし、関数を関手とする圏の集まり」として述べてきた
- Haskellを構成しているのはHaskだけではない
- こちらのExamples of categoriesを見てみれば、以下のようにずらりと並ぶ。そして、Haskellの作り全体が圏論に基づいていると見ることができる、と読み取れる
  - Set, the category of sets and set functions.
  - Mon, the category of monoids and monoid morphisms.
  - Monoids are themselves one-object categories.
  - Grp, the category of groups and group morphisms.
  - Rng, the category of rings and ring morphisms.
  - Grph, the category of graphs and graph morphisms.
  - Top, the category of topological spaces and continuous maps.
  - Preord, the category of preorders and order preserving maps.
  - CPO, the category of complete partial orders and continuous functions.
  - Cat, the category of categories and functors.
  - Hask
  - the category of data types and functions on data structures
  - the category of functions and data flows (~ data flow diagram)
  - the category of stateful objects and dependencies (~ object diagram)
  - the category of values and value constructors
  - the category of states and messages (~ state diagram)
モナドの位置づけ
- Haskellの説明では、モナドに力点が置かれることがある
- モナドも関手の一種であって、上記で説明してきたように、圏と圏とを対応付ける点では同じ
- モナドが他の関手と違うのは、圏Ｃを、「同じ圏Ｃ」に関手で対応付ける点
- モナドは圏Ｃを圏Ｃに対応付けるが、ＣとＣが同じでわかりにくいのでＣ１、Ｃ２と書き分ければ、Ｃ１をＣ２に対応付ける関手
- Ｃ１の全オブジェクトに二つの射がある
  - （１）Ｃ１のオブジェクトをモナド対応するＣ２のオブジェクトに写す射。Ｃ１とＣ２とが同じ圏なので、モナドで対応付けるという手続きが入っているけれど、Ｃ１＝Ｃ２の内部の射の作用の結果と見ることもできる
    - これは、「モナド作用を１回かぶせる」ことに相当する
    - unitと呼ばれる
  - （２）もう一つの射は、「モナド作用をマイナス１回かぶせる」ことに相当する射
    - モナドを作用させて、さらに作用させても、同じ圏に落ちる。Ｃ１がＣ２になってさらにＣ３になる。このＣ３としてのオブジェクトをＣ２で対応するオブジェクトに写す射もある(Ｃ２＝Ｃ３だから)。このような射
    - join と呼ばれる
- 注意するべきは、このunit,joinはＣ１＝Ｃ２＝Ｃ３の圏の中で考えれば、射〜関数だが、Ｃ１をＣ２に対応付ける関手(Ｃ１＝Ｃ２なのでモナド)の作用とみれば、モナドに備わった作用であること
- モナドという関手を定義するときには、この射であって関手であるものを持つことが必要なので、この作用が定義されている(定義されて初めてモナドとなる)
- 以下のようなモナドの定義がある。２つの作用(unitとjoin)を定めればよいはずなのに、unitは定義されているけれど(return :: a -> ma)、joinが定義されずに、(>>=)が定義されている。この(>>=)はbindと呼ばれる作用。
  - 実は、このbindを定義すればjoinを定義しつつ、どんな処理がしたいかが定義できていることになる。したがって、これでＯＫ。

class Functor m => Monad m where
  return :: a -> m a
  (>>=)  :: m a -> (a -> m b) -> m b

- - bindの定義とjoinとの関係は

join :: Monad m => m (m a) -> m a
join x = x >>= id

(>>=) :: Monad m => m a -> (a -> m b) -> m b
x >>= f = join (fmap f x)

- 例で考えよう
  - 集合Ｓがあって、そのべき集合を考える
    - S={s1,s2,...}
    - P(S)={{},{s1},{s2},...,{s1,s2},{s1,s3},...,{s1,s2,...}}
    - ここで、圏はs1,s2,...をオブジェクトとしている
    - プレーンな集合とそのべき集合とは、同じオブジェクトによって成り立つ、2つの世界
    - この2つの世界は同じオブジェクトで成り立っているから、そのオブジェクト同士に射があるような圏は共通
    - 今、SからP(S)への対応付けとして、『Ｓの要素siは、P(S)の要素{si}に対応付ける』というものを採用する(Ａ）
    - また、P(S)の要素に対して、そのべき集合を考える。P(P(S))={{},{{s1}},{{s2}},...,{{s1},{s2}},...}のような
    - ここで、入れ子がくどいので、{{s1},{s2}}は{s1,s2}にすることにすれば、それはP(S)の要素。このように『無駄な(無駄に見える)入れ子を外す』処理も定義する(Ｂ)
  - この(Ａ)がunitで(Ｂ)がjoinに相当する
  - リストが多重になっているときにそれを外すのも同様
- リストも集合も、要素数が不定であるが、その曖昧なことに対応する仕組みがリストのモナド。この曖昧対応性をMaybeなどに使えばMaybe モナド
- このモナドのよいところは、処理を連結して、その途中のいつ、うまくいかなくなるかがわからないときに、それをかませておけば、エラーを吐いたりしやすいこと。そのよさが、立ち位置として目立たせ、モナド向けのdo記法があったりする
  - モナドに関してより詳しくはこちら
Haskellを出発点に圏論を学ぶにはこちら