Haskell Language
Schémas de récursivité

Remarques

Points fixes

Fix prend un type "template" et lie le nœud récursif, superposant le gabarit comme une lasagne.

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

Dans un Fix f on trouve une couche du gabarit f . Pour remplir f paramètre d », Fix f bouchons en soi. Alors , quand vous regardez à l' intérieur du modèle f vous trouvez un événement récurrent de Fix f .

Voici comment un type de données récursif typique peut être traduit dans notre structure de modèles et de points fixes. Nous supprimons les occurrences récursives du type et marquons leurs positions en utilisant le paramètre 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)

Plier une structure une couche à la fois

Catamorphismes , ou replis , modèle récursif primitif. cata déchire un point de repère couche par couche, en utilisant une fonction d' algèbre (ou une fonction de pliage ) pour traiter chaque couche. cata nécessite une instance Functor pour le type de modèle 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

Déplier une structure une couche à la fois

Les anamorphismes , ou se déploient, modélisent la corécursion primitive. ana construit un point de repère couche par couche, en utilisant une fonction Coalgebra (ou une fonction de déploiement ) pour produire chaque nouveau calque. ana nécessite une instance Functor pour le type de modèle 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

Notez que ana et cata sont doubles . Les types et les implémentations sont des images en miroir les uns des autres.

Dépliage puis pliage, fusionné

Il est courant de structurer un programme en créant une structure de données, puis en la réduisant à une valeur unique. Cela s'appelle un hylomorphisme ou un repli . Il est possible d'éliminer complètement la structure intermédiaire pour améliorer l'efficacité.

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

Dérivation:

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

Récursivité primitive

Les paramorphismes modélisent la récursivité primitive. A chaque itération du pli, la fonction de pliage reçoit le sous-arbre pour un traitement ultérieur.

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

Les tails du prélude peuvent être modélisées en tant que paramorphisme.

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

Corecursion primitive

Les apomorphismes modélisent la corécursion primitive. A chaque itération du dépliage, la fonction dépliante peut renvoyer une nouvelle graine ou un sous-arbre entier.

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

Notez que apo et para sont doubles . Les flèches du type sont retournées; le tuple dans para est double à l'un Either à l' Either dans l' apo , et les implémentations sont des images miroir l'une de l'autre.