Haskell Language
Schemi di ricorsione
Ricerca…
Osservazioni
Le funzioni menzionate qui negli esempi sono definite con vari gradi di astrazione in diversi pacchetti, ad esempio recursion-schemes
data-fix
e recursion-schemes
(più funzioni qui). È possibile visualizzare un elenco più completo cercando su Hayoo .
Punti fissi
Fix
prende un tipo di "modello" e lega il nodo ricorsivo, stratificando il modello come una lasagna.
newtype Fix f = Fix { unFix :: f (Fix f) }
All'interno di una Fix f
troviamo un livello del modello f
. Per compilare f
parametro s', Fix f
tappi in sé. Quindi quando guardi all'interno del modello f
trovi un'occorrenza ricorsiva di Fix f
.
Ecco come un tipico tipo di dati ricorsivo può essere tradotto nella nostra struttura di modelli e punti fissi. Rimuoviamo ricorrenze ricorsive del tipo e segniamo le loro posizioni usando il parametro 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)
Piegare una struttura uno strato alla volta
Catamorfismi , o pieghe , modello di ricorsione primitiva. cata
strappa un fixpoint strato per strato, usando una funzione algebra (o funzione di piegatura ) per elaborare ogni livello. cata
richiede un'istanza Functor
per il tipo di modello 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
Aprire una struttura uno strato alla volta
Anamorphisms, o si dispiega, modello corecursion primitiva. ana
crea un fixpoint strato per strato, usando una funzione di coalgebra (o una funzione di dispiegamento ) per produrre ogni nuovo livello. ana
richiede un'istanza Functor
per il tipo di modello 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
Nota che ana
e cata
sono duali . I tipi e le implementazioni sono immagini speculari l'una dell'altra.
Spiegando e poi piegando, fuso
È normale strutturare un programma come costruzione di una struttura dati e quindi comprimerlo in un singolo valore. Questo è chiamato un hylomorphism o ripiegare . È possibile elidere la struttura intermedia complessivamente per migliorare l'efficienza.
hylo :: Functor f => (a -> f a) -> (f b -> b) -> a -> b
hylo f g = g . fmap (hylo f g) . f -- no mention of Fix!
Derivazione:
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
Ricorsione primitiva
I paramorfismi modellano la ricorsione primitiva. Ad ogni iterazione della piega, la funzione di piegatura riceve la sottostruttura per ulteriori elaborazioni.
para :: Functor f => (f (Fix f, a) -> a) -> Fix f -> a
para f = f . fmap (\x -> (x, para f x)) . unFix
Le tails
del Preludio possono essere modellate come un paramorfismo.
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 primitivo
Gli apomorfismi modellano il corecursion primitivo. Ad ogni iterazione dello spiegamento, la funzione di spiegamento può restituire un nuovo seme o un'intera sottostruttura.
apo :: Functor f => (a -> f (Either (Fix f) a)) -> a -> Fix f
apo f = Fix . fmap (either id (apo f)) . f
Nota che apo
e para
sono duali . Le frecce nel tipo sono capovolte; la tupla in para
è duale Either
in apo
e le implementazioni sono immagini speculari l'una dell'altra.