---
title: Recursion Scheme の紹介
tags: 
author: [グミ](https://convert.docswell.com/user/GummyCandy1206)
site: [Docswell](https://www.docswell.com/)
thumbnail: https://bcdn.docswell.com/page/P7XXZ6G47X.jpg?width=480
description: Recursion Scheme の紹介 by グミ
published: January 16, 26
canonical: https://convert.docswell.com/s/GummyCandy1206/KJQ7Q1-2026-01-17-recursion-scheme
---
# Page. 1

![Page Image](https://bcdn.docswell.com/page/P7XXZ6G47X.jpg)

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


# Page. 2

![Page Image](https://bcdn.docswell.com/page/37KW814P7D.jpg)

はじめに


# Page. 3

![Page Image](https://bcdn.docswell.com/page/LJ312QL4E5.jpg)

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


# Page. 4

![Page Image](https://bcdn.docswell.com/page/8JDXZ9N57G.jpg)

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


# Page. 5

![Page Image](https://bcdn.docswell.com/page/VEPPDZ5DE8.jpg)

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


# Page. 6

![Page Image](https://bcdn.docswell.com/page/27V21WPG7Q.jpg)

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


# Page. 7

![Page Image](https://bcdn.docswell.com/page/5JGR2DQD7L.jpg)

foldr


# Page. 8

![Page Image](https://bcdn.docswell.com/page/47QVP1KXEP.jpg)

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


# Page. 9

![Page Image](https://bcdn.docswell.com/page/KE4MYRP271.jpg)

計算の流れ
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


# Page. 10

![Page Image](https://bcdn.docswell.com/page/L7186Q9KJG.jpg)

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


# Page. 11

![Page Image](https://bcdn.docswell.com/page/G7WZWMQP72.jpg)

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


# Page. 12

![Page Image](https://bcdn.docswell.com/page/4JZ15QW6E3.jpg)

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


# Page. 13

![Page Image](https://bcdn.docswell.com/page/YE6L96GL7V.jpg)

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


# Page. 14

![Page Image](https://bcdn.docswell.com/page/GE51N6VMJ4.jpg)

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


# Page. 15

![Page Image](https://bcdn.docswell.com/page/97215M3RER.jpg)

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


# Page. 16

![Page Image](https://bcdn.docswell.com/page/DJYZKX15EM.jpg)

リストの和に対応する例
foldr (+) 0 [1,2,3]に対応する例は以下の通り。
newtype Fix f = Fix { unFix :: f (Fix f) }
cata :: Functor f =&gt; (f a -&gt; a) -&gt; Fix f -&gt; a
cata f = f . fmap (cata f) . unFix
data ListF a b = Nil | Cons a b deriving (Functor)
listSumAlgebra :: ListF Int Int -&gt; 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


# Page. 17

![Page Image](https://bcdn.docswell.com/page/V7N3R12478.jpg)

計算の流れ
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


# Page. 18

![Page Image](https://bcdn.docswell.com/page/YJ99M514J3.jpg)

計算の流れ
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


# Page. 19

![Page Image](https://bcdn.docswell.com/page/GJ89LY4VED.jpg)

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


# Page. 20

![Page Image](https://bcdn.docswell.com/page/LJLWL46R7R.jpg)

圏論で見る cata


# Page. 21

![Page Image](https://bcdn.docswell.com/page/47M9MK5PJW.jpg)

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


# Page. 22

![Page Image](https://bcdn.docswell.com/page/P7RGVX3YJ9.jpg)

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


# Page. 23

![Page Image](https://bcdn.docswell.com/page/PJXXZ644JX.jpg)

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


# Page. 24

![Page Image](https://bcdn.docswell.com/page/3JKW81ZPJD.jpg)

可換図式
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


# Page. 25

![Page Image](https://bcdn.docswell.com/page/LE312QD475.jpg)

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


# Page. 26

![Page Image](https://bcdn.docswell.com/page/8EDXZ9P5JG.jpg)

可換図式
(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


# Page. 27

![Page Image](https://bcdn.docswell.com/page/V7PPDZND78.jpg)

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


# Page. 28

![Page Image](https://bcdn.docswell.com/page/2JV21WKGJQ.jpg)

𝐹 代数


# Page. 29

![Page Image](https://bcdn.docswell.com/page/5EGR2D9DJL.jpg)

𝐹 代数について
関手𝐹 : 𝐶 → 𝐶に対して、対象𝑎 ∈ 𝐶と射𝑓 : 𝐹 𝑎 → 𝑎の組
(𝑎, 𝑓)を𝐹 代数と呼ぶ。
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


# Page. 30

![Page Image](https://bcdn.docswell.com/page/4JQVP1WX7P.jpg)

𝐹 代数の射
𝐹 代数の射𝜑 : (𝑎, 𝑓) → (𝑏, 𝑔)は圏𝐶の射𝜑 : 𝑎 → 𝑏であって、
𝜑 ∘ 𝑓 = 𝐹 𝜑 ∘ 𝑔を満たすもの。
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


# Page. 31

![Page Image](https://bcdn.docswell.com/page/K74MYRK2J1.jpg)

𝐹 代数の射
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


# Page. 32

![Page Image](https://bcdn.docswell.com/page/LJ186QXKEG.jpg)

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


# Page. 33

![Page Image](https://bcdn.docswell.com/page/GJWZWMNPJ2.jpg)

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


# Page. 34

![Page Image](https://bcdn.docswell.com/page/4EZ15Q3673.jpg)

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


# Page. 35

![Page Image](https://bcdn.docswell.com/page/Y76L96XLJV.jpg)

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


# Page. 36

![Page Image](https://bcdn.docswell.com/page/G751N6XME4.jpg)

全体のまとめ


# Page. 37

![Page Image](https://bcdn.docswell.com/page/9J215MXR7R.jpg)

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


# Page. 38

![Page Image](https://bcdn.docswell.com/page/DEYZKX857M.jpg)

補記


# Page. 39

![Page Image](https://bcdn.docswell.com/page/VJN3R1Q4J8.jpg)

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


# Page. 40

![Page Image](https://bcdn.docswell.com/page/YE99M5D4E3.jpg)

リスト以外の型に対する 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


# Page. 41

![Page Image](https://bcdn.docswell.com/page/GE89LY3V7D.jpg)

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


# Page. 42

![Page Image](https://bcdn.docswell.com/page/LELWL4VRJR.jpg)

リスト以外の例
リストだけだと cata のメリットが分かりづらい。 他の例と
して、抽象構文木を文字列に変換する例を見る。
data ExprF x = LitF Int | AddF x x | MulF x x deriving (Functor)
type Expr = Fix ExprF
astToStr :: ExprF String -&gt; String
astToStr (LitF n)
= show n
astToStr (AddF a b) = &quot;(&quot; ++ a ++ &quot; + &quot; ++ b ++ &quot;)&quot;
astToStr (MulF a b) = &quot;(&quot; ++ a ++ &quot; × &quot; ++ b ++ &quot;)&quot;
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


