Haskell Language
Recursieschema's

Opmerkingen

Vaste punten

Fix neemt een "sjabloon" type en bindt de recursieve knoop, waarbij de sjabloon als een lasagne wordt gelaagd.

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

Binnen een Fix f vinden we een laag van de sjabloon f . Invullen f 's parameter Fix f pluggen op zich. Dus als u in de sjabloon f kijkt, vindt u een recursief voorkomen van Fix f .

Hier is hoe een typisch recursief datatype kan worden vertaald in ons raamwerk van sjablonen en vaste punten. We verwijderen recursieve gebeurtenissen van het type en markeren hun posities met de 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)

Een structuur laag voor laag opvouwen

Catamorfismen , of plooien , modelleren primitieve recursie. cata tranen in een plaatsbepalingspunt laag voor laag, via een algebra functie (of vouwen functie) aan elke laag te verwerken. cata vereist een Functor instantie voor het sjabloontype 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

Een structuur laag voor laag ontvouwen

Anamorfismen , of ontvouwt zich , modelleert primitieve corecursie. ana bouwt een plaatsbepalingspunt laag voor laag, via een coalgebra functie (of ontvouwen functie) aan elke nieuwe laag te produceren. ana vereist een Functor instantie voor het sjabloontype 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

Merk op dat ana en cata dubbel zijn . De typen en implementaties zijn spiegelbeelden van elkaar.

Uitvouwen en vervolgens vouwen, gefuseerd

Het is gebruikelijk om een programma te structureren als het opbouwen van een gegevensstructuur en deze vervolgens samen te vouwen tot een enkele waarde. Dit wordt een hylomorfisme of hervouwen genoemd . Het is mogelijk om de tussenliggende structuur helemaal te elimineren voor verbeterde efficiëntie.

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

Afleiding:

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

Primitieve recursie

Paramorfismen modelleren primitieve recursie. Bij elke iteratie van de vouw ontvangt de vouwfunctie de substructuur voor verdere verwerking.

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

De tails de Prelude kunnen worden gemodelleerd als een paramorfisme.

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

Primitieve corecursie

Apomorfismen modelleren primitieve corecursie. Bij elke iteratie van het ontvouwen, kan de ontvouwende functie ofwel een nieuw zaad of een hele subtree teruggeven.

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

Merk op dat apo en para dubbel zijn . De pijlen in het type zijn omgedraaid; de tuple in para is tweeledig ten opzichte van Either in apo , en de implementaties zijn spiegelbeelden van elkaar.