Haskell Language
Rekursionsscheman

Anmärkningar

Fasta punkter

Fix tar en "mall" -typ och binder den rekursiva knuten och lägger mallen som en lasagne.

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

Inuti en Fix f hittar vi ett lager av mallen f . För att fylla i f : s parameter, Fix f pluggar i sig själv . Så när du tittar in i mallen f hittar du en rekursiv förekomst av Fix f .

Så här kan en typisk rekursiv datatyp översättas till vår ram av mallar och fasta punkter. Vi tar bort rekursiva händelser av typen och markerar deras positioner med parametern 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)

Vik upp en struktur ett lager åt gången

Katamorfismer , eller veck , modellerar primitiv rekursion. cata rivar ned ett fixpoint lager för lager med hjälp av en algebrafunktion (eller vikningsfunktion ) för att bearbeta varje lager. cata kräver en Functor instans för Functor 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

Ta bort en struktur ett lager åt gången

Anamorfismer , eller utvecklas , modellerar primitiv corecursion. ana bygger upp ett fixpoint lager för lager med hjälp av en kolbrafunktion (eller utvecklingsfunktion ) för att producera varje nytt lager. ana kräver en Functor instans för 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

Observera att ana och cata är dubbla . Typerna och implementeringarna är spegelbilder av varandra.

Fällas ut och sedan fällas, smält

Det är vanligt att strukturera ett program som att bygga upp en datastruktur och sedan kollapsa det till ett enda värde. Detta kallas hylomorfism eller återveckling . Det är möjligt att eliminera mellanstrukturen helt och hållet för att förbättra effektiviteten.

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

Härledning:

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

Primitiv rekursion

Paramorfismer modellerar primitiv rekursion. Vid varje iteration av vikningen får vikningsfunktionen undertråden för vidare bearbetning.

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

Preludens tails kan modelleras som en paramorfism.

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

Primitiv corecursion

Apomorfismer modellerar primitiv corecursion. Vid varje iteration av utspelningen kan utfoldningsfunktionen returnera antingen ett nytt frö eller en hel undertråd.

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

Observera att apo och para är dubbla . Pilarna i typen är vända; tupeln i para är dubbel mot Either i apo , och implementeringarna är spegelbilder av varandra.