再帰スキーム

programming-paradigmtype-theory

再帰的データ構造に対する再帰のパターンを、catamorphism / anamorphism などの高階関数として抽象化したもの。「再帰の構造を型で捉え、手書きの再帰を畳み込み/展開の宣言に置き換える」。出典は “Functional Programming with Bananas, Lenses, Envelopes and Barbed Wire” (Meijer ら 1991)。

基本スキーム

スキーム別名代数/余代数の型役割
catamorphismfoldf a -> a で畳む構造を消費して値に（ADT の fold）
anamorphismunfolda -> f a で生む種から構造を生成
hylomorphismana then cataa -> f a ＆ f b -> b中間構造を介す。中間を消せる（deforestation）
paramorphism—f (Fix f, a) -> afold + 元の部分構造も同時に参照（cata の一般化）
apomorphism—a -> f (Either (Fix f) a)unfold + Left で部分木を即返し早期終了（ana の一般化）
zygomorphism—補助代数つき cata2つの fold を相互依存で同時に走らせる
histomorphism—f (Cofree f a) -> afold + 過去の全中間結果を参照（動的計画法）

para/apo は cata/ana の双対対: para は「畳みつつ元の構造を見る」、apo は「生みつつ既存構造で打ち切る」。f (Fix f, a) の Fix f（元の部分構造）と、Either (Fix f) a の Left (Fix f)（生成停止して既存を流用）が双対になっている。

コード — cata / ana / hylo（Haskell 風）

不動点 Fix f と関手 f を使い、再帰を1段ぶん剥がす/包む unFix/Fix の上にスキームを定義する。

newtype Fix f = Fix { unFix :: f (Fix f) }

type Algebra   f a = f a -> a      -- 1段の構造をまとめ上げる
type Coalgebra f a = a -> f a      -- 種から1段ぶん構造を生む

cata :: Functor f => Algebra f a -> Fix f -> a
cata alg = alg . fmap (cata alg) . unFix
--                 └ 部分構造を先に再帰で畳んでから alg で1段まとめる

ana :: Functor f => Coalgebra f a -> a -> Fix f
ana coalg = Fix . fmap (ana coalg) . coalg
--                 └ coalg で1段生み、各 seed をさらに再帰展開

hylo :: Functor f => Algebra f b -> Coalgebra f a -> a -> b
hylo alg coalg = alg . fmap (hylo alg coalg) . coalg
--    Fix を経由せず ana→cata を融合（中間構造を作らない＝deforestation）

具体例: 自然数の関手 f a = One | Succ a を畳む sum、種から木を生む例。

-- リストの基底関手: data ListF a r = Nil | Cons a r  (Fix (ListF a) ≅ [a])
sumAlg :: Algebra (ListF Int) Int
sumAlg Nil         = 0
sumAlg (Cons x acc) = x + acc          -- acc は「残りを既に畳んだ結果」
-- total = cata sumAlg someList

-- factorial を hylo で: ana で [n, n-1, ..., 1] を生み、cata で積を取る（中間リスト無し）
fact :: Int -> Int
fact = hylo prodAlg rangeCoalg
  where rangeCoalg 0 = Nil
        rangeCoalg n = Cons n (n-1)
        prodAlg Nil          = 1
        prodAlg (Cons x acc) = x * acc

圏論の背景

データ型を関手 f の不動点 Fix f と見る。

なぜ重要か

関連

押さえどころ（カード化候補）

Graph

Backlinks