今日は 圏論勉強会 第2回 の日です

圏論勉強会ではないモノイド勉・・・いや、圏論勉強会 第2回に来ました。資料とustreamは公開されています。

第2回: モノイド・群 / 講師 @9_ties さん

• モノイド、圏は計算機に必要な概念
  • 対象が1つの圏。シンプルだけどシンプル過ぎない圏
• 約束: 自然数は0以上。Haskell的なセクションの記法を使う
• モノイド: (M, ・)の組。結合率、単位元
  • M は台集合
• モノイドの例
  • 自然数(N, +), (N, ×)
  • 整数、有理数、実数、複素数も同様
  • Aの要素の有限列と、++
    • ([1,2] ++ [3, 4]) ++ [5,6] == [1,2] ++ ([3,4]++[5,6])
    • []が単位元
  • 文字列も同様
  • 論理和(単位元false)、論理積(単位元true)
  • 集合の∪(単位元Φ)と∩(単位元A)。(ただし、冪集合P(A)の元を使う)
  • max(単位元は最小値)、min(単位元は最大値)
  • 「有界半束はモノイド」
• データ列の集約・集積演算はモノイドと関連: folding
  • sum、filter、min、max、any、allなどなど
  • 直列化できるコンテナであれば、モノイドで畳み込みができる
  • 結合性により、部分列から畳み込む事ができる → 並列計算に応用できる
• 実用上はmapでモノイドの値にマッピングしてから畳み込む
  • foldMapという関数でOK
  • Data.Treeの例。IntはMonoidじゃないので、Sum*1にmapするといい
  • foldMap Sum tree でOK。
  • 接点を数える foldMap (\x -> Sum 1) tree
  • リストにする foldMap (\x -> [x]) tree
  • 集合にする foldMap (\x -> Data.Set.singleton x) tree
  • 論理 foldMap (All . even) tree、foldMap (Any . even) tree、
  • タプル foldMap (\x -> (Sum x, Product x)) tree
  • 文字列もモノイド foldMap show tree
• モノイドでできること、できないこと
  • 画像の集合から画像の集合への写像を集積すれば絵を描ける
  • ロボットの状態の集合からロボットの状態の集合への写像を集積すればロボットを操作できる
  • オートマトンとかでも。となると、正規表現も。
• endomorphism(自己準同型写像): ドメインとコドメインが同じ集合である
  • End(A)はモノイド(作用素モノイドの一例)
• instance Monoid (End a)が標準ライブラリに！
  • appEndo (foldMap (\x -> if even x then End (* x) else End (+ x)) tree) 0
  • 足し算とかけ算を混ぜられるようになった
  • 1つの"モノ"に対して、それを変化させる写像を集めると"モノ"イドになっている
• endmorphismで任意のモノイドを表せそう
  • 1 + 2 + 3 == (1 +) . (2 +) . (3 +)
  • これをきちんとした言葉で述べたい
• モノイド準同型 : モノイドからモノイドへの構造を保ったマッピング*2
  • 二項演算と単位元を保つ
  • 例 length:([A], ++) → (N, +)
• モノイドの同型
  • 同型写像: 準同型fで、f.g=id, g.f=id なるgがあるもの
  • 例: f(x) = 2^x。 f: (N,+) → ({2^n}, ×)
  • log により、かけ算を足し算にできるね、という話。天文学者の寿命が倍になったと言われた
• 部分モノイド: 台集合に包含関係がある2つのモノイド
• 定理: 任意のモノイドは、適当な集合AについてEnd Aの部分モノイドと同型
  • 表現定理の一例(線形写像を行列で表現、なども)。正体が掴みやすくなる
  • 米田の補題への第一歩
• 証明:
  • Mにたいして、a→(a・)を考えると、(a・).(b・) = (a.b・)、(e・) = idよりa→(a・)は準同型
  • 逆に(a・)→(a・)(e)を考えるとこれも準同型
  • 合成するとidになるので同型
• (・a)でとる場合は、反モノイド(合成を逆にとる)にする必要がある
• foldrとfoldl → 畳込みなのでモノイドと関連するはず
  • foldrはA×B→B、foldlはB×A→Bをとる
  • foldrで(p・).(q・).(r・)と書き直すと、End Bのなすモノイドになっている
  • foldlでは逆
  • 自己準同型へのマッピングをしていると考えられる
• 例: (1 :)、(2 :)、(3 :)みたいな作用を畳み込みたい
  • foldr (\x -> (x :)) [] [1, 2, 3]
  • 2が来たら捨てるような操作も → foldr (\x -> if x == 2 then const else (x :)) [1, 2, 3]
• foldrやfoldlは足し算とかに使うものではない。endomorphismのモノイドを生かして使うべき
• すべてfoldrでいい！という考え方ではダメ
  • foldrのB→Bの部分にありとあらゆるモノイドが存在する。
  • 何でも書けるが汎用的過ぎる。個性的なモノイドを生かさないと可哀想
  • (a×)と(+b)のendmorphismからなるモノイド → ax + bなモノイド。
  • つまり (a, b)・(c, d) := (ac, ad + b)とするとモノイドになる*3
  • foldMapで扱える
  • foldMapは並列化しやすいが、foldrは代入するので並列化しにくい、というのもある
• foldMap fも列のモノイドからのモノイド準同型
  • 列は特別。ありとあらゆる畳み込みが列のモノイドからできる
  • 列のモノイドは自由モノイドの性質を持つ
• 抽象的な自由モノイドの定義
  • 列のモノイドは、長さ1の列で現せる。情報が失われていない
  • モノイド準同型から、長さ1の列のマッピングがあれば、全ての列をマッピングできる
• ([A], ++) → (M,・) / A → M 随伴関係
  • i(a) = [a] とすると、 foldMap f . i = fが可換であれば、モノイド準同型foldMap fは唯一存在する。
• 自由モノイドは同型を除いて一意。列・連結からなるモノイドと同じと見なせる
• プログラムもモノイド(2項演算は文を並べる事。単位元は何もしない)
  • モナドは自己関(以下略
• 群 : モノイド。逆元(inverse)が存在
• 群の例
  • Z、Q、R、Cと足し算
  • Q/{0}、R/{0}とかけ算
  • 逆に、(N, +)、(N,×)、([A], ++)は群ではない
  • 正二面体群: 正3角形。120度回転、対称移動、恒等変換、を組み合わせると群
  • 対称性を表すものが群
  • 暗号: 文章の集合のhomomorphismであるAut。復号化できる=群。逆元の計算が困難な部分群を探す事が強力な暗号を探す事
• Aut(automorphism)とは・・・全単射なhomomorphism。自己同型写像
  • Aut(X)は自己同型写像を集めた群
• 定理: 群Aは集合AについてAut(A)の部分群と同型
• 対称群 Sym(A):集合上の自己同型群、置換群: 対称群の部分群
  • 数値で表せる。分解できる→計算機で扱いやすい
• ケイリーの定理: 任意の群は適当な置換群と同型
  • 先ほどの定理と同じことを言っているが置換は計算機で扱いやすいのがポイント
• 有限群(= ルービックキューブ、48次対称群)を持参しました。
  • 3カ所のみ色を変えるデモ
  • 置換群と同型のはず。構造を調べる
  • できること、できないことは群の構造をみるとわかる
• 今日の話はAwodeyの1章。結構読めるようになったのでは？

*1:Productもある

*2:関手になる

*3:アフィン変換が畳み込める