Haskell Language
再帰スキーム

備考

固定小数点

Fixは「テンプレート」タイプを取り、再帰的な結び目を結びつけ、テンプレートをラナグのように重ね合わせます。

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

Fix f中で、テンプレートfレイヤーを見つける。 fのパラメータを入力するには、 Fix fプラグ自体を Fix fします 。だから、テンプレートf内部を見ると、 Fix f再帰的な出現が見つかります。

ここでは典型的な再帰的データ型を、テンプレートと固定小数点のフレームワークにどのように変換できるかを示します。型の再帰的な出現を取り除き、 rパラメータを使用してその位置をマークします。

{-# LANGUAGE DeriveFunctor #-}

-- natural numbers
-- data Nat = Zero | Suc Nat
data NatF r = Zero_ | Suc_ r deriving Functor
type Nat = Fix NatF

zero :: Nat
zero = Fix Zero_
suc :: Nat -> Nat
suc n = Fix (Suc_ n)


-- lists: note the additional type parameter a
-- data List a = Nil | Cons a (List a)
data ListF a r = Nil_ | Cons_ a r deriving Functor
type List a = Fix (ListF a)

nil :: List a
nil = Fix Nil_
cons :: a -> List a -> List a
cons x xs = Fix (Cons_ x xs)


-- binary trees: note two recursive occurrences
-- data Tree a = Leaf | Node (Tree a) a (Tree a)
data TreeF a r = Leaf_ | Node_ r a r deriving Functor
type Tree a = Fix (TreeF a)

leaf :: Tree a
leaf = Fix Leaf_
node :: Tree a -> a -> Tree a -> Tree a
node l x r = Fix (Node_ l x r)

一度に1つのレイヤーを折りたたむ

Catamorphisms 、またはフォールド 、モデルの基本的な再帰。 cataそれぞれの層を処理するために代数関数（又は折り関数 ） を用いて、層によって不動点層を切断します。 cataはテンプレート型f Functorインスタンスが必要です。

cata :: Functor f => (f a -> a) -> Fix f -> a
cata f = f . fmap (cata f) . unFix

-- list example
foldr :: (a -> b -> b) -> b -> List a -> b
foldr f z = cata alg
    where alg Nil_ = z
          alg (Cons_ x acc) = f x acc

一度に1つのレイヤーを展開する

Anamorphisms、または展開する 、モデルプリミティブcorecursion。 anaそれぞれの新しい層を生成する余代数の関数（または展開関数 ） を用いて、層によって不動点層を構築します。 ana必要とFunctorテンプレート型のインスタンスをf 。

ana :: Functor f => (a -> f a) -> a -> Fix f
ana f = Fix . fmap (ana f) . f

-- list example
unfoldr :: (b -> Maybe (a, b)) -> b -> List a
unfoldr f = ana coalg
    where coalg x = case f x of
                         Nothing -> Nil_
                         Just (x, y) -> Cons_ x y

anaとcataはデュアルです。タイプと実装は互いに鏡像です。

展開してから折りたたむ

プログラムを構造化してデータ構造を構築し、それを単一の値に折り畳むことは一般的です。これは、 ハイロモフィズムまたはリフォールドと呼ばれます。効率を向上させるために、中間構造を完全に排除することが可能です。

hylo :: Functor f => (a -> f a) -> (f b -> b) -> a -> b
hylo f g = g . fmap (hylo f g) . f  -- no mention of Fix!

導出：

hylo f g = cata g . ana f
         = g . fmap (cata g) . unFix . Fix . fmap (ana f) . f  -- definition of cata and ana
         = g . fmap (cata g) . fmap (ana f) . f  -- unfix . Fix = id
         = g . fmap (cata g . ana f) . f  -- Functor law
         = g . fmap (hylo f g) . f  -- definition of hylo

プリミティブ再帰

Paramorphismsはプリミティブ再帰をモデル化します。フォールドの各反復において、フォールディング関数は、さらなる処理のためにサブツリーを受け取る。

para :: Functor f => (f (Fix f, a) -> a) -> Fix f -> a
para f = f . fmap (\x -> (x, para f x)) . unFix

Preludeのtailsは、パラアロピズムとしてモデル化することができます。

tails :: List a -> List (List a)
tails = para alg
    where alg Nil_ = cons nil nil  -- [[]]
          alg (Cons_ x (xs, xss)) = cons (cons x xs) xss  -- (x:xs):xss

原始核巡視

Apomorphismsモデルプリミティブcorecursion。アンフォールディングの各反復で、アンフォールディング関数は新しいシードまたはサブツリー全体を返すことがあります。

apo :: Functor f => (a -> f (Either (Fix f) a)) -> a -> Fix f
apo f = Fix . fmap (either id (apo f)) . f

apoとparaはデュアルであることに注意してください。タイプの矢印が反転します。 paraのタプルはapoのEitherにデュアルであり、実装はお互いの鏡像です。