Haskell Language
Rekursionsschemata

Bemerkungen

Fixpunkte

Fix nimmt einen "Vorlagen" -Typ und bindet den rekursiven Knoten, wobei die Vorlage wie eine Lasagne geschichtet wird.

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

In einem Fix f finden wir eine Ebene der Vorlage f . In füllen f ‚s - Parameter, Fix f Stecker in sich. Wenn Sie also in die Vorlage f schauen, finden Sie ein rekursives Vorkommen von Fix f .

So kann ein typischer rekursiver Datentyp in unser Framework aus Vorlagen und Fixpunkten übersetzt werden. Wir entfernen rekursive Vorkommen des Typs und markieren ihre Positionen mit dem Parameter 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)

Schicht für Schicht eine Struktur zusammenfalten

Katamorphismen oder Falten modellieren die primitive Rekursion. cata reißt ein Fixpunktes Schicht für Schicht nach unten, eine algebraischen Funktion (oder Faltungsfunktion) unter Verwendung von jeder Schicht zu verarbeiten. cata erfordert eine Functor Instanz für den Vorlagentyp f .

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

Eine Schicht Schicht für Schicht entfalten

Anamorphismen modellieren primitive Corecursion oder entfalten sich . ana baut einen Fixpunkt Schicht für Schicht auf und verwendet eine Coalgebra- Funktion (oder Entfaltungsfunktion ), um jede neue Ebene zu erzeugen. ana erfordert eine Functor Instanz für den Vorlagentyp 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

Beachten Sie, dass ana und cata dual sind . Die Typen und Implementierungen sind Spiegelbilder voneinander.

Entfalten und dann falten, verschmolzen

Es ist üblich, ein Programm so zu strukturieren, dass es eine Datenstruktur aufbaut und diese dann auf einen einzelnen Wert reduziert. Dies wird als Hylomorphismus oder Rückfaltung bezeichnet . Es ist möglich, die Zwischenstruktur insgesamt zu entfernen, um die Effizienz zu verbessern.

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

Ableitung:

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

Primitive Rekursion

Paramorphismen modellieren primitive Rekursion. Bei jeder Wiederholung der Faltung erhält die Faltfunktion den Teilbaum zur weiteren Verarbeitung.

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

Die tails des Präludiums können als Paramorphismus modelliert werden.

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

Primitive Kernflucht

Apomorphismen modellieren primitive Kernursachen. Bei jeder Wiederholung der Entfaltung kann die Entfaltungsfunktion entweder einen neuen Samen oder einen ganzen Unterbaum zurückgeben.

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

Beachten Sie, dass apo und para dual sind . Die Pfeile im Typ werden umgedreht; das Tupel in para zu dem Dual Either in apo , und die Implementierungen sind Spiegelbilder voneinander.