Haskell Language
Schémas de récursivité
Recherche…
Remarques
Les fonctions mentionnées ici dans les exemples sont définies avec des degrés d'abstraction variables dans plusieurs packages, par exemple les recursion-schemes
data-fix
et de recursion-schemes
(plus de fonctions ici). Vous pouvez afficher une liste plus complète en effectuant une recherche sur Hayoo .
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.