Haskellと圏論：パフォーマンス改善からKan拡張へ

Haskell と圏論： パフォーマンス改善から Kan 拡張へ グミ@GummyCandy1206 関数型まつり 2026 2026-07-11 #fp_matsuri_b 1 / 67

自己紹介 グミ @GummyCandy1206 • 富山県のエンジニア • 好きな言語: Haskell, Lean • 趣味で関数型と圏論を勉強しています。 • 仕事でも関数型使いたい！ 最近は圏論の Kan 拡張と Haskell の関係について勉強していまし た。この発表ではそのことについて話します。 2 / 67

Haskell は圏論に由来するいくつかの概念を取り入れている。 例えば… 圏論における、対象と射 Haskell における、型と関数 id𝐴 id 𝐴 a 𝑓 id𝐵 f 𝑔∘𝑓 𝐵 id 𝑔 g . f b g 𝐶 c id𝐶 id 3 / 67

もちろん、それだけではなく… 圏論における、Functor 𝐹 id𝐴 Haskell における、Functor 𝐹𝐴 f a 𝐹𝑓 𝐹 id𝐵 fmap f 𝐹 (𝑔 ∘ 𝑓) 𝐹𝐵 fmap id fmap id 𝐹𝑔 fmap (g . f) f b fmap g 𝐹𝐶 f c 𝐹 id𝐶 fmap id 4 / 67

他にも… 圏論 Haskell 自然変換𝛼 : 𝐹 ⇒ 𝐺 多相関数 forall a. f a -> g a モナド(𝑇 , 𝜂, 𝜇) Monad m 5 / 67

一方で、圏論には次の有名な言葉がある。 We end with the observations that all concepts of category theory are Kan extensions. — Mac Lane, Saunders. Categories for the Working Mathematician. 圏論におけるすべての概念は Kan 拡張！ 6 / 67

圏論は Haskell に影響を与えている。 Haskell 影響 圏論 7 / 67

一方で、圏論におけるすべての概念は Kan 拡張である。 Haskell 影響 圏論 すべての概念 8 / 67 Kan 拡張

では、Haskell の概念も Kan 拡張として理解できるのでは？ Haskell ? 影響 圏論 すべての概念 9 / 67 Kan 拡張

“Haskell Kan extension”で調べてみると、なんと Kan 拡張に関する Haskell のパッケージが見つかる！ 参考：https://hackage.haskell.org/package/kan-extensions 10 / 67

• https://hackage.haskell.org/package/kan-extensions

この発表のゴール kan-extensions パッケージのコードを通じて、 Haskell と Kan 拡張の関係を理解する。 11 / 67

Data.Functor.Kan.Ran に右 Kan 拡張が定義されている。 1 newtype 2 Ran g h a = Ran { runRan :: forall b. (a -> g b) -> h b } 12 / 67

1 newtype 2 Ran g h a = Ran { runRan :: forall b. (a -> g b) -> h b } 一見しただけでは • どのように利用できるのかがわからない • 圏論の右 Kan 拡張との関係が分からない kan-extensions の中でも簡単で具体的な例から徐々に一般化して Haskell と Kan 拡張の関係を観察する。 13 / 67

Yoneda 14 / 67

次のようなコードを考える。 1 import Debug.Trace 2 3 data Box a = Box [a] deriving Show 4 5 6 instance Functor Box where fmap f (Box xs) = trace "重い処理" $ Box (fmap f xs) 7 8 9 g :: Int -> Int g x = x + 1 10 11 12 13 14 15 plain :: Box Int plain = fmap g $ fmap g $ fmap g $ Box [1,2] つまり、fmap が重い場合を考える。 （Box は説明用に定義した Functor） 15 / 67

このコードの実行結果は以下の通り。 1 ghci> plain 2 重い処理 3 重い処理 4 重い処理 5 Box [4,5] 重い処理が 3 回呼び出されている。 16 / 67

先程のコードの plain を次のように修正する。 1 import Data.Functor.Yoneda 2 yoneda :: Box Int 4 yoneda = lowerYoneda $ 5 fmap g $ 6 fmap g $ 7 fmap g $ 8 liftYoneda $ 9 Box [1,2] 3 kan-extensions の Data.Functor.Yoneda で定義された関数を利用する。 17 / 67

修正は 2 箇所だけ。 plain :: Box Int 2 plain = fmap g $ 3 fmap g $ 4 fmap g $ 5 Box [1,2] 1 6 yoneda :: Box Int 8 yoneda = lowerYoneda $ 9 fmap g $ 10 fmap g $ 11 fmap g $ 12 liftYoneda $ 13 Box [1,2] 7 liftYoneda と lowerYoneda が追加されている。 18 / 67

修正後のコードの実行結果は以下の通り。 1 ghci> yoneda 2 重い処理 3 Box [4,5] 重い処理の呼び出しが 1 回だけになった。 一方で、出力結果に変化はない。 計算結果を変えずに高速化できた！ 19 / 67

高速化の謎を探るため、liftYoneda と lowerYoneda の実装を調べる。 liftYoneda :: Functor f => f a -> Yoneda f a 2 liftYoneda a = Yoneda (\f -> fmap f a) 1 3 lowerYoneda :: Yoneda f a -> f a 5 lowerYoneda (Yoneda f) = f id 4 参考：https://hackage-content.haskell.org/package/kan-extensions-5.2.8/docs/src/Data.Functor.Yoneda.html 20 / 67

• https://hackage-content.haskell.org/package/kan-extensions-5.2.8/docs/src/Data.Functor.Yoneda.html

図で書くと… liftYoneda f a Yoneda f a lowerYoneda f a == [Int]の場合は… liftYoneda [Int] Yoneda [] Int lowerYoneda 21 / 67

具体例 [Int]の例として、[1,2]を考える。 liftYoneda [1,2] Yoneda (\f -> fmap f [1,2]) fmap id [1,2] Yoneda (\f -> fmap f [1,2]) lowerYoneda liftYoneda と lowerYoneda は互いに逆関数になっている。 22 / 67

yoneda は右図の赤い経路で計算している。 liftYoneda Box Int yoneda :: Box Int 2 yoneda = lowerYoneda $ 3 fmap g $ 4 fmap g $ 5 fmap g $ 6 liftYoneda $ 7 Box [1,2] Yoneda Box Int 1 fmap g Box Int Yoneda Box Int fmap g 高速化の理由を調べるため、Yoneda f の fmap の定義を確認する。 Box Int fmap g Yoneda Box Int fmap g Box Int fmap g Yoneda Box Int lowerYoneda 23 / 67 fmap g

Yoneda f の fmap の定義 instance Functor (Yoneda f) where 2 fmap f m = Yoneda (\k -> runYoneda m (k . f)) 1 Yoneda の定義 newtype Yoneda f a 2 = Yoneda { runYoneda :: forall b. (a -> b) -> f b } 1 参考：https://hackage-content.haskell.org/package/kan-extensions-5.2.8/docs/src/Data.Functor.Yoneda.html 24 / 67

• https://hackage-content.haskell.org/package/kan-extensions-5.2.8/docs/src/Data.Functor.Yoneda.html

具体例 g x = x + 1 として考える。 liftYoneda [1,2] Yoneda (\f -> fmap f [1,2]) fmap g fmap g [2,3] fmap (id.g) [1,2] Yoneda (\f -> fmap (f.g) [1,2]) lowerYoneda 25 / 67

fmap g を繰り返す場合 liftYoneda xs Yoneda (\f -> fmap f xs) fmap g fmap g fmap g xs Yoneda (\f -> fmap (f.g) xs) fmap g fmap g (fmap g xs) fmap g fmap ((id.g).g) xs Yoneda (\f -> fmap ((f.g).g) xs) lowerYoneda fmap が満たすべき性質 (fmap f) . (fmap g) == fmap (f . g) 26 / 67

パフォーマンス改善の理由 Yoneda を経由することで、fmap g の合成が、g の合成の fmap に変 わった。 重い fmap g の処理が 1 回だけになり、パフォーマンスが 改善した。 (fmap g) . (fmap g) . (fmap g) 改善 fmap (g . g . g) 27 / 67

注意 実際には Yoneda を用いたからといって直ちに fmap の合成のパ フォーマンスが改善するわけではない。 GHC は fmap の合成を自動で最適化することがあるため、工夫しな くても十分に速い場合がある。 28 / 67

ここまでのまとめ • Haskell と Kan 拡張の関係を知りたい • Kan 拡張に関するパッケージ kan-extensions がある • kan-extensions パッケージの使い道を知りたい • 使い道の一つとして、Yoneda を用いた fmap の合成を最適化する例 がある • Yoneda は fmap の合成を合成の fmap に変換することで fmap の回数 を 1 回にまとめることができる 29 / 67

Codensity 30 / 67

🙇 謝罪 プロポーザルでは Codensity でパフォーマンス改善する具体例を紹 介すると書いていましたが、時間が足りないことと数式を並べるよ りも良い説明を思いつかないことから割愛いたします。 この発表では具体例ではなく概要だけを紹介します。 31 / 67

ここまで、fmap の合成の最適化について扱った。 ↓ fmap 以外はどうか？ Codensity を用いると、次のような例について同様の最適化ができ る。 ((m >>= k1) >>= k2) >>= k3 32 / 67

Codensity は Yoneda と似たような感じで定義されている。 newtype Yoneda f a = Yoneda 2 { runYoneda :: forall b. (a -> b) -> f b } 1 3 newtype Codensity m a = Codensity 5 { runCodensity :: forall b. (a -> m b) -> m b } 4 参考：https://hackage-content.haskell.org/package/kan-extensions-5.2.8/docs/src/Control.Monad.Codensity.html 33 / 67

• https://hackage-content.haskell.org/package/kan-extensions-5.2.8/docs/src/Control.Monad.Codensity.html

fmap の合成は Yoneda を経由することで合成の fmap に変換できた。 変換 (fmap g) . (fmap f) fmap (g . f) (>>=)の合成(m >>= k) >>= h は Codensity を経由することで次の形 に変換できる。 変換 (m >>= k) >>= h m >>= (\x -> k x >>= h) (>>=)が満たすべき性質(m >>= k) >>= h ≡ m >>= (\x -> k x >>= h) 34 / 67

Codensity を経由することで、(>>=)の計算方法を変えることができ る。 m >>= k の処理が重い場合、これを回避することでパフォーマ ンスを改善することができる。 (m >>= k) >>= h 改善 m >>= (\x -> k x >>= h) 35 / 67

ここまでのまとめ • Yoneda とよく似た Codensity が kan-extensions に存在する。 • fmap の合成は Yoneda で高速化できる • (>>=)の合成は Codensity で高速化できる 36 / 67

Ran 37 / 67

Yoneda と Codensity はよく似ている。 newtype Yoneda 2 = Yoneda 1 f a { runYoneda :: forall b. (a -> b) -> f b } 3 newtype Codensity m a 5 = Codensity { runCodensity :: forall b. (a -> m b) -> m b } 4 38 / 67

R を次のように定義すると、この 2 つを一般化できそう。 newtype Yoneda 2 = Yoneda 1 f a { runYoneda :: forall b. (a -> b) -> f b } 3 newtype Codensity m a 5 = Codensity { runCodensity :: forall b. (a -> m b) -> m b } 4 6 newtype R 8 = R 7 g h a { run :: forall b. (a -> g b) -> h b } 39 / 67

実はこの R こそが、kan-extensions で定義されている右 Kan 拡張 Ran g h a。 newtype Ran g h a 2 = Ran { runRan :: forall b. (a -> g b) -> h b } 1 Yoneda f a ≅ Ran Identity f a Codensity g a ≅ Ran g g a Ran は Yoneda と Codensity の一般化になっている。 40 / 67

あとは、Ran が圏論の右 Kan 拡張に対応していることを確認すれば よい。 次の順番で確認する。 • Ran g h a を圏論的に表すとHom (Hom (𝑎, 𝐺 −), 𝐻) • 右 Kan 拡張の随伴より、上記がHom(Hom(𝑎, −), Ran𝐺 𝐻)と同型 • 米田の補題より、上記がRan𝐺 𝐻(𝑎)と同型 41 / 67

Haskell と圏論の関係を見るために、Haskell の型、関数などを圏論 の言葉で書き直す。 • 型 a は対象 𝑎 • 関数 a -> b は Hom (𝑎, 𝑏) の元。 • f a は 関手 𝐹 で 𝑎を移したもの 𝐹 (𝑎) に対応する。 • forall a. f a -> g a は自然変換 Hom (𝐹 , 𝐺) に対応する。 ※厳密には違うと思うが、一旦これで進める。 42 / 67

Haskell の右 Kan 拡張の定義は以下のとおり。
newtype Ran g h a
2
= Ran { runRan :: forall b. (a -> g b) -> h b }
1

これを圏の言葉に書き換えると、次のようになる。
Hom (Hom (𝑎, 𝐺 −), 𝐻)

43 / 67

• Ran g h a を圏論的に表すとHom (Hom (𝑎, 𝐺 −), 𝐻) ←OK • 右 Kan 拡張の随伴より、上記がHom(Hom(𝑎, −), Ran𝐺 𝐻)と同型 • 米田の補題より、上記がRan𝐺 𝐻(𝑎)と同型 44 / 67

圏論における右 Kan 拡張の定義 𝐶, 𝐷, 𝐸を圏として、𝐺 : 𝐶 → 𝐷, 𝐻 : 𝐶 → 𝐸を関手とする。 𝐷 𝐺 𝐶 𝐻 45 / 67 𝐸

次の 2 つの条件を満たす(Ran𝐺 𝐻, 𝜀)を𝐺に沿った𝐻の右 Kan 拡張 と呼ぶ。 1. Ran𝐺 𝐻は関手𝐷 → 𝐸で、𝜀は自然変換Ran𝐺 𝐻 ∘ 𝐺 ⇒ 𝐻 46 / 67

2. 関手𝑆 : 𝐷 → 𝐸と、自然変換𝜃 : 𝑆 ∘ 𝐺 ⇒ 𝐻に対して、次を満たす 自然変換𝜏 : 𝑆 ⇒ Ran𝐺 𝐻が一意に存在する。 𝜃 = 𝜀 ∘ 𝜏𝐺 47 / 67

𝐻をRan𝐺 𝐻に送る関手をRan𝐺 で表す。 関手𝐶 → 𝐸からなる圏を𝐸 𝐶 のように書くと、Ran𝐺 は関手𝐸 𝐶 → 𝐸𝐷。 𝐷 Ran𝐺 𝐻 𝐺 𝐶 𝐻 𝐸𝐶 𝐸 48 / 67 Ran𝐺 𝐸𝐷

関手Ran𝐺 : 𝐸 𝐶 → 𝐸 𝐷 には随伴関手（良い性質を持つ逆向きの関手） がある。 𝐺−1 : 𝐸 𝐷 → 𝐸 𝐶 を𝑆 ↦ 𝑆 ∘ 𝐺とすると、𝐺−1 はRan𝐺 の左随 伴になる。 49 / 67

議論しやすいように、Haskell の圏 Hask の代わりに 集合の圏 Set で考える。 𝐸をSetに置き換える。 𝐷 Ran𝐺 𝐻 𝐺 𝐺−1 𝐶 𝐻 Set𝐶 Set Set𝐷 Ran𝐺 50 / 67

随伴と𝐺−1 ⊣ Ran𝐺 と、随伴の定義より任意の𝑆 ∈ 𝐸 𝐷 と𝐻 ∈ 𝐸 𝐶 に 対して、以下が成り立つ。 HomSet𝐶 (𝐺−1 𝑆, 𝐻) ≅ HomSet𝐷 (𝑆, Ran𝐺 𝐻) 𝑆は任意なので、𝑆 = Hom𝐷 (𝑎, −) でも成り立つ。 HomSet𝐶 (𝐺−1 Hom𝐷 (𝑎, −), 𝐻) ≅ HomSet𝐷 (Hom𝐷 (𝑎, −), Ran𝐺 𝐻) ※任意の𝑏 ∈ 𝐷に対して、Hom𝐷 (𝑎, 𝑏)は集合であると仮定する。つまり、𝐷は局所小圏とす る。 51 / 67

𝐺−1 : 𝐸 𝐷 → 𝐸 𝐶 は𝑆 ↦ 𝑆 ∘ 𝐺なので、次のように書き換えられる。 HomSet𝐶 (𝐺−1 Hom𝐷 (𝑎, −), 𝐻) = HomSet𝐶 (Hom𝐷 (𝑎, 𝐺 −), 𝐻) まとめると HomSet𝐶 (Hom𝐷 (𝑎, 𝐺 −), 𝐻) = HomSet𝐶 (𝐺−1 Hom𝐷 (𝑎, −), 𝐻) （𝐺−1 に書き換え） ≅ HomSet𝐷 (Hom𝐷 (𝑎, −), Ran𝐺 𝐻) 52 / 67 (𝐺−1 ⊣ Ran𝐺 )

• Ran g h a を圏論的に表すとHom (Hom (𝑎, 𝐺 −), 𝐻) ←OK • 右 Kan 拡張の随伴より、上記がHom(Hom(𝑎, −), Ran𝐺 𝐻)と同型 ←OK • 米田の補題より、上記がRan𝐺 𝐻(𝑎)と同型 53 / 67

示すべきこと HomSet𝐷 (Hom𝐷 (𝑎, −), Ran𝐺 𝐻) ≅ Ran𝐺 𝐻(𝑎) これは米田の補題より成り立つ。 米田の補題 𝐷を局所小圏、𝐹 : 𝐷 → Setを関手とする。このとき次が成り立つ。 HomSet𝐷 (Hom𝐷 (𝑎, −), 𝐹 ) ≅ 𝐹 (𝑎) 54 / 67

Yoneda と米田の補題の関係
Yoneda f a = Yoneda { runYoneda :: forall b. (a -> b) -> f b }
liftYoneda
f a

Yoneda f a
lowerYoneda

𝐹 (𝑎)

HomSet𝐷 (Hom𝐷 (𝑎, −), 𝐹 )

55 / 67

• Ran g h a を圏論的に表すとHom (Hom (𝑎, 𝐺 −), 𝐻) ←OK • 右 Kan 拡張の随伴より、上記がHom(Hom(𝑎, −), Ran𝐺 𝐻)と同型 ←OK • 米田の補題より、上記がRan𝐺 𝐻(𝑎)と同型 ←OK 56 / 67

まとめ 集合の圏Setを Haskell の圏だと思うと、Ran g h a と右 Kan 拡張 Ran𝐺 𝐻(𝑎)が同型であることを確認できる。 HomSet𝐶 (Hom𝐷 (𝑎, 𝐺 −), 𝐻) （Haskell の右 Kan 拡張） ≅ HomSet𝐷 (Hom𝐷 (𝑎, −), Ran𝐺 𝐻) (𝐺−1 ⊣ Ran𝐺 ) ≅ Ran𝐺 𝐻(𝑎) （米田の補題） 57 / 67

まとめ 58 / 67

最初の問い Haskell の概念も Kan 拡張として理解できるのでは？ Haskell ? 影響 圏論 すべての概念 59 / 67 Kan 拡張

パフォーマンス改善に利用できる Yoneda や Codensity が Kan 拡張 の例となっている。 Haskell 影響 圏論 Yoneda、Codensity など すべての概念 60 / 67 Kan 拡張

まとめ • Yoneda は fmap の合成のパフォーマンスを改善できる • Codensity は(>>=)の合成のパフォーマンスを改善できる • Ran は Yoneda と Codensity の一般化である • Ran と右 Kan 拡張の対応は、右 Kan 拡張の随伴と米田の補題を用 いて示せる ご清聴ありがとうございました。 61 / 67

余談 Haskell 影響 圏論 すべての概念 この状況は Kan 拡張チャンス!!である。 62 / 67 Kan 拡張

Haskell 影響 圏論 Ran影響 すべての概念 すべての概念 Kan 拡張 「実はこの発表内容自体が Kan 拡張になっていたのだ」と言えると 面白かったが、これは過言。 63 / 67

すべての概念は Kan 拡張 Kan 拡張の例 • 関手𝐹 : 𝐶 → 𝐷が右随伴を持つとき、その右随伴はLan𝐹 id𝐶 • 関手𝐺 : 𝐷 → 𝐶が左随伴を持つとき、その左随伴はRan𝐺 id𝐷 • 極限は右 Kan 拡張 • 余極限は左 Kan 拡張 随伴も極限も抽象的な概念。 64 / 67

随伴の例 極限の例 • 自由群関手は忘却関手の左随 伴 • 集合𝐴に対して− × 𝐴は(−)𝐴 の 左随伴 • 終対象 • 直積 • 等化子 • 引き戻し • 逆極限 65 / 67

終対象の例 直積の例 逆極限の例 • 一元集合 • 自明群（始対象で もある） • 整数の整除関係の 圏における 0 • Unit 型 () • 集合の直積 • 位相空間の直積 • 整数の整除関係の 圏における最大公 約数 • タプル (a,b) • 𝑝-進整数 • 副有限群 66 / 67

参考文献 [1] alg-d. Kan 拡張. https://alg-d.com/math/kan_extension/kan_extension.pdf. [2] Bartosz Milewski. Kan Extensions | Bartosz Milewski’s Programming Cafe. https:// bartoszmilewski.com/2017/04/17/kan-extensions/. [3] Edward A. Kmett. Kan-extensions. https://hackage.haskell.org/package/kanextensions. [4] Saunders Mac lane and Saunders Maclane. Categories for the working mathematician, Vol. 5. Springer, 1971. [5] Tom Leinster. ベーシック圏論, 丸善出版, 2017. 67 / 67

• https://alg-d.com/math/kan_extension/kan_extension.pdf
• https://bartoszmilewski.com/2017/04/17/kan-extensions/
• https://hackage.haskell.org/package/kan-extensions