Recursion Scheme の紹介

Recursion Scheme の紹介 λ Kansai in Winter 2026 - 2026-01-17 グミ (@GummyCandy1206)

はじめに

はじめに 動機 • LT 会での発表の経験がほぼないので、発表したい • 関数型プログラミングに興味がある ↓ λ Kansai in Winter 2026 が凄くちょうどよい！ 3/42

本スライドで紹介すること • Recursion Scheme（再帰関数から再帰に関する部分だけ を抜き出して抽象化したもの） • 本スライドでは特に foldr の一般化である catamorphism について紹介する 4/42

個人的おもしろポイント • 圏論をプログラミングに応用している例である ‣ 圏論の言葉を用いることでシンプルに説明できる ‣ 可換になるように定義すると、正しいコードになる ‣ 双対や射の合成によって、新たなアルゴリズムが生まれ る 5/42

仮定する事前知識 • Haskell の基礎知識（Functor、型クラスなど） • 圏論の基礎知識（関手、始対象など） 6/42

foldr

foldr たし算やかけ算、文字列の結合などの二項演算を各要素に順 番に適用する関数 foldr (+) 0 [1,2,3] == 6 -- すべてたす foldr (*) 1 [2,3,4] == 24 -- すべてかける foldr (++) "" ["Hello ","World!"] == "Hello World!" -- すべて結合する 8/42

計算の流れ foldr (+) 0 [1,2,3] 1 + foldr (+) 0 [2,3] 1 + (2 + foldr (+) 0 [3]) 1 + (2 + (3 + foldr (+) 0 [])) 1 + (2 + (3 + 0)) 1 + (2 + 3) 1 + 5 6 foldr は再帰的に計算する。 9/42

リストについてもう少し詳しく リスト型は以下のように定義されている。 data List a = [] | a : List a リスト型は再帰的に定義されている。 リスト[1,2,3]の表記はシンタックスシュガーなので、定義 に戻したものを確認する。 [1,2,3] == 1 : (2 : (3 : [])) 10/42

ここまでのまとめ • foldr は再帰的に計算する • リスト型は再帰的に定義されている 11/42

再帰と再帰以外に分離する

ListF List の再帰的な構造を再帰に関する部分とそれ以外の部分 に分ける。 data List a = [] | a : List a -- ↓ 再帰とそれ以外に分解 newtype Fix f = Fix { unFix :: f (Fix f) } -- 再帰に関する部分 data ListF a b = Nil | Cons a b deriving (Functor) -- 再帰以外の部分 Fix (ListF a)が List a に対応している。 13/42

List と ListF の対応 [1,2,3]は ListF では次のように書ける。 Fix (Cons 1 (Fix (Cons 2 (Fix (Cons 3 (Fix Nil)))))) nil = Fix Nil、cons a b = Fix (Cons a b)とすれば、リス トとの対応がわかりやすい。 1 : (2 : (3 : [] )) :: List a 1 `cons` (2 `cons` (3 `cons` nil)) :: Fix (ListF a) 14/42

catamorphism の定義 foldr の一般化である catamorphism を定義する。 以降、 cata と表記する。 foldr :: Foldable t => (a -> b -> b) -> b -> t a -> b cata :: Functor f => (f a -> a) -> Fix f -> a cata f = f . fmap (cata f) . unFix これだけ見ても foldr の一般化であることは分かりづらい。 証明も少し面倒なので、計算例をいくつか見るだけにしてお く。 15/42

リストの和に対応する例
foldr (+) 0 [1,2,3]に対応する例は以下の通り。
newtype Fix f = Fix { unFix :: f (Fix f) }
cata :: Functor f => (f a -> a) -> Fix f -> a
cata f = f . fmap (cata f) . unFix
data ListF a b = Nil | Cons a b deriving (Functor)
listSumAlgebra :: ListF Int Int -> Int
listSumAlgebra Nil
= 0
listSumAlgebra (Cons a b) = a + b
main = do
let xs = Fix (Cons 1 (Fix (Cons 2 (Fix (Cons 3 (Fix Nil))))))
print (cata listSumAlgebra xs) -- 6

16/42

計算の流れ cata listSumAlgebra (Fix Nil) (listSumAlgebra . fmap (cata listSumAlgebra) . unFix ) (Fix Nil) (listSumAlgebra . fmap (cata listSumAlgebra)) (unFix (Fix Nil)) (listSumAlgebra . fmap (cata listSumAlgebra)) Nil listSumAlgebra (fmap (cata listSumAlgebra) Nil) listSumAlgebra Nil 0 これは foldr (+) 0 [] == 0 に対応している。 17/42

計算の流れ x :: a 、xs :: Fix (ListF a)とする。 このとき、Fix (Cons x xs)について計算してみる。 cata listSumAlgebra (Fix (Cons x xs)) (listSumAlgebra . fmap (cata listSumAlgebra) . unFix ) (Fix (Cons x xs)) (listSumAlgebra . fmap (cata listSumAlgebra)) (unFix (Fix (Cons x xs))) (listSumAlgebra . fmap (cata listSumAlgebra)) (Cons x xs) listSumAlgebra ((fmap (cata listSumAlgebra)) (Cons x xs)) listSumAlgebra (Cons x (cata listSumAlgebra xs)) x + cata listSumAlgebra xs これは foldr (+) 0 (x:xs) == x + foldr (+) 0 xs に対応し ている。 18/42

ここまでのまとめ • List は再帰に関する部分の Fix とそれ以外の部分の ListF に分解できる。 • foldr (+) 0 は再帰に関する部分の cata とそれ以外の部分 の listSumAlgebra に分解できる。 19/42

圏論で見る cata

cata の定義 newtype Fix f = Fix { unFix :: f (Fix f) } cata :: Functor f => (f a -> a) -> Fix f -> a cata f = f . fmap (cata f) . unFix cata の定義が初見時に理解できなかったので、圏論を用い て大雑把に説明する。 21/42

可換図式 簡単のために、a = Int、b = Int の場合を考える。 foldr (+) 0 :: [Int] -> Int の catamorphism バージョン を考える。 [Int] Fix (ListF Int) foldr (+) 0 ? ↑ ↑ Int Int 22/42

可換図式 右の図式を関手 ListF Int で移す。 fmap ? Fix (ListF Int) ? ↑ (ListF Int) (Fix (ListF Int)) ListF Int ↑ ↑ ListF Int Int Int 23/42

可換図式 unFix の定義より、以下の矢印がある。 (ListF Int) (Fix (ListF Int)) ↑ newtype Fix f = Fix { unFix :: f (Fix f) } unFix Fix (ListF Int) fmap ? ? ↑ ↑ ListF Int Int Int 24/42

可換図式 もし、f :: ListF Int Int -> Int という関数を与えると、 以下の図式を可換にする ? は次の等式を満たす。 (ListF Int) (Fix (ListF Int)) ↑ ? == f . (fmap ?) . unFix unFix Fix (ListF Int) fmap ? ↑ f ↑ ↑ ListF Int Int ? Int 25/42

可換図式 (ListF Int) (Fix (ListF Int)) ↑ ? を cata f と書けば、cata f == f . (fmap (cata f)) . unFix となるが、これは cata f の定義そのもの。 unFix Fix (ListF Int) fmap (cata f) ↑ f ↑ ↑ ListF Int Int cata f Int 定義の説明としては不十分だと思うが、図式が可換になるよ うに考えると定義が導かれる。 26/42

ここまでのまとめ • 図式が可換になるように考えると、自然に cata の定義が 得られる。 27/42

𝐹 代数

𝐹 代数について 関手𝐹 : 𝐶 → 𝐶に対して、対象𝑎 ∈ 𝐶と射𝑓 : 𝐹 𝑎 → 𝑎の組 (𝑎, 𝑓)を𝐹 代数と呼ぶ。 Fix ↑ ↑ (ListF Int) (Fix (ListF Int)) unFix Fix (ListF Int) fmap (cata f) ↑ f ↑ ↑ ListF Int Int cata f Int ListF Int は関手なので、(Fix (ListF Int), Fix)や(Int,f) は(ListF Int)代数である。 29/42

𝐹 代数の射 𝐹 代数の射𝜑 : (𝑎, 𝑓) → (𝑏, 𝑔)は圏𝐶の射𝜑 : 𝑎 → 𝑏であって、 𝜑 ∘ 𝑓 = 𝐹 𝜑 ∘ 𝑔を満たすもの。 Fix ↑ ↑ (ListF Int) (Fix (ListF Int)) unFix Fix (ListF Int) fmap (cata f) ↑ f ↑ ↑ ListF Int Int cata f Int cata f は(ListF Int)代数の射である。 30/42

𝐹 代数の射 Fix ↑ ↑ (ListF Int) (Fix (ListF Int)) unFix Fix (ListF Int) fmap (cata f) ↑ f ↑ ↑ ListF Int Int cata f Int 実は、(Fix (ListF Int), Fix)は(ListF Int)代数の始対象と なっている（𝐹 始代数）。 cata f は始対象からの唯一の射で ある。 31/42

anamorphism catamorphism の図式の双対は、anamorphism と呼ばれる （以降、ana と表記する）。 Fix ↑ (ListF Int) (Fix (ListF Int)) ↑ ListF Int Int ana f ↑ fmap (ana f) Fix (ListF Int) ↑ f Int 双対を考えることで、新たなアルゴリズムを得られる。 32/42

hylomorpshism cata f と ana g の合成を考えることで新たなアルゴリズムが 得られる。 hylo f g = cata f . ana g 一度リストを作って、それを畳み込むイメージ。 （例） 𝑛以下の整数のリストの積（階乗） 33/42

metamorphism cata f と ana g の合成の順番を逆にすることで別のアルゴリ ズムが得られる。 meta f g = ana f . cata g 一度集約してそれを展開するイメージ。 （例） • AtCoder のある問題を metamorphism で考えた例 連長圧 縮したリスト上の分割(Haskell) その他にも様々な morphism が考えられている。 34/42

• https://zenn.dev/nobsun/articles/runlength-2025-07-09

ここまでのまとめ • Fix (ListF Int)は ListF Int 代数の始対象。 • cata は始対象からの唯一の射。 • 双対や射の合成で、新たなアルゴリズムが得られる。 35/42

全体のまとめ

まとめ • Recursion Scheme は再帰とそれ以外に分離して考える • catamorphism は foldr の一般化である • 図式が可換になるように考えると、勝手に catamorphism の定義を導ける • catamorphism は圏論（𝐹 代数）を用いるとシンプルに説 明できる • 双対や射の合成で新たなアルゴリズムを得られる ↓ 関数型プログラミングと圏論の両方の学習者にとって面白い 例 ご清聴ありがとうございました。 37/42

補記

foldr の型 foldr :: Foldable t => (a -> b -> b) -> b -> t a -> b foldr (+) 0 [1,2,3] -- 6 Foldable はリストの一般化。 リストとは限らないが、 toList :: Foldable t => t a -> [a]でリストにできる。 リ ストっぽい型と思うことができる。 39/42

リスト以外の型に対する foldr 二分木の値の和を求める例。 1 2 4 3 Empty {-# LANGUAGE DeriveFoldable #-} data Tree a = Empty | Leaf a | Node (Tree a) a (Tree a) deriving Foldable tree = Node (Node (Leaf 4) 2 Empty) 1 (Leaf 3) main = do print (foldr (+) 0 tree) -- 10 リストでなくても計算できる！ 40/42

ListF a が Functor であることについて ListF の定義の deriving 宣言で Functor であることを宣言し ている。 data ListF a b = Nil | Cons a b deriving (Functor) 初見時に混乱したので、少し補足しておく。 ListF が Functor になるのではなく、ListF a が Functor になる。 以下のような自明な Functor が導出される。 instance Functor (ListF a) where fmap f Nil = Nil fmap f (Cons a b) = Cons a (f b) 41/42

リスト以外の例 リストだけだと cata のメリットが分かりづらい。 他の例と して、抽象構文木を文字列に変換する例を見る。 data ExprF x = LitF Int | AddF x x | MulF x x deriving (Functor) type Expr = Fix ExprF astToStr :: ExprF String -> String astToStr (LitF n) = show n astToStr (AddF a b) = "(" ++ a ++ " + " ++ b ++ ")" astToStr (MulF a b) = "(" ++ a ++ " × " ++ b ++ ")" ast :: Expr ast = Fix (AddF (Fix (MulF (Fix (LitF 1)) (Fix (LitF 2)))) (Fix (AddF (Fix (LitF 3)) (Fix (LitF 4))))) main = do putStrLn (cata astToStr ast) -- ((1 × 2) + (3 + 4)) 42/42