Haskellの圏論における準同型性 - プログラミング学習サイト

定義

準同型写像（homomorphism）とは、「代数的な構造を保ったまま、ある構造から別の構造へ移す写像」のことです。つまり、「元の世界での計算の仕方」が「移った先の世界」でも矛盾なく成り立つようにする写像です。

群 (G,⋅) と群 (H,∗) の間の写像 f:G→H が群準同型であるとは

f(x⋅y)=f(x)∗f(y)

が成り立つということである。

直感的な理解

「群準同型」っていうのは、

世界A : 群G の演算
世界B : 群H の演算

という「ルールのあるゲーム」どうしをつなぐ関数。その関数 f に「演算のルールを壊さないこと」を求めるのが準同型性。

成り立つ条件

群Gと、その中で成立する演算 ⋅ がある

閉じている（閉包性）
- 任意のb∈G に対して a⋅b∈G。
結合法則
- 任意の a,b,c∈G に対して (a⋅b)⋅c=a⋅(b⋅c)
単位元の存在
- e∈G が存在して、任意の a∈G に対して e⋅a=a⋅e=a
逆元の存在
- a∈G に対して、ある b∈G が存在して a⋅b=b⋅a=e

群の特徴は「必ず逆元が存在する」こと。

これはプログラミングで「取り消し・ロールバック・Undo機能」を設計するときにめっちゃ役立ちます。
- 文字列編集の Undo
- トランザクションのロールバック
- ゲームの「一手戻す」

これらは「操作の集合が群をなす」とみなすと自然に設計できます。

圏論における準同型性

-- 整数に1を足す関数
f :: Int -> Int
f x = x + 1

-- 整数を2倍にする関数
g :: Int -> Int
g x = x * 2

main = do
    let myarray = [10, 11, 12, 13]
    print ( fmap (f.g)  myarray )
    print ( fmap  f (fmap (g)  myarray)  )

実行結果は以下の通り

[21,23,25,27]
[21,23,25,27]

(f.g) を fmap で適用するのと、g を fmap で適用してから f を fmap で適用するのは、圏論的に同じ操作となります。

関数合成の順番がどちらでも同じ結果となることがわかる。これを準同型性と呼ぶ。

最も重要なことは、Haskellにおけるfmap関数は準同型性が成り立つため、 fmapに対する関数は入れ替えることが可能 という性質が成り立ち得るという考えだ。

mapとリストについての準同型性

fmap func [a1, a2, a3...] = [func(a1), func(a2), func(a3)] - (1)

(fmap f (fmap g myarray) ) = (fmap f.g myarray)

myarray = [a1, a2, a3...] とする。

(fmap f (fmap g myarray) ) => (fmap f (fmap g [a1, a2, a3...])) --- 関数gに対して(1)を適応 => (fmap f ([g(a1), g(a2), g(a3)...])) --- 関数fに対して(1)を適応 => [f(g(a1)), f(g(a2)), f(g(a3))...] => [(f.g)(a1), (f.g)(a2), (f.g)(a3)...] => (fmap f.g [a1, a2, a3...]) => (fmap f.g myarray)

mapと文字列の準同型性

main = do
    let mystring = "This is pen"
    print ( fmap (length.(split " ")  mystring )
    print ( fmap  length (fmap (split " ")  myarray)  )

fmapとmaybe型の準同型性

maybe型におけるfmapの定義は以下の通り

fmap f (Just x) = Just (f x)
fmap _ Nothing  = Nothing

1) fmap (*2) (Just 4) の値を求めよ

fmap (*2) (Just 4)
= Just ( (*2) 4)
= Just 8

2) (fmap (+1) ( fmap (*2) (Just 4)) )の値を求めよ

(fmap (+1) ( fmap (*2) (Just 4)) )
= (fmap (+1) ( Just 8) )
= (Just 9)

3) fmap *1 (Just 4) の値を求めよ

fmap ((+1).(*2)) (Just 4)
= (Just 4*2 + 1)
= (Just 9)

4) 次を証明せよ

(fmap f (fmap g (Just x) ) ) = (fmap f.g (Just x))

(fmap f (fmap g (Just x) ) ) 
= (fmap f (Just g(x)) )
= (Just f(g(x)))
= (Just f.g(x))
= (fmap f.g (Just x))

逆写像の一意制を示せ

f ∈ 圏(A,B)
g ∈ 圏(B,A)
g.f = 1(A)
f.g = 1(B)

この時、AとBは同系である。

page:https://minegishirei.hatenablog.com/entry/2025/04/06/182301

*1:+1).(*2