Haskell Language
Esquemas de recursion
Buscar..
Observaciones
Las funciones mencionadas aquí en los ejemplos se definen con distintos grados de abstracción en varios paquetes, por ejemplo, data-fix
y recursion-schemes
(más funciones aquí). Puedes ver una lista más completa buscando en Hayoo .
Puntos fijos
Fix
toma un tipo de "plantilla" y ata el nudo recursivo, colocando la plantilla en capas como una lasaña.
newtype Fix f = Fix { unFix :: f (Fix f) }
Dentro de una Fix f
encontramos una capa de la plantilla f
. Para rellenar f
parámetro 's, Fix f
tapones en sí mismo. Así que cuando se mira dentro de la plantilla f
encontrará una ocurrencia recursiva de Fix f
.
Aquí es cómo un tipo de datos recursivo típico se puede traducir en nuestro marco de plantillas y puntos fijos. Eliminamos las apariciones recursivas del tipo y marcamos sus posiciones usando el parámetro 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)
Doblando una estructura de una capa a la vez
Catamorfismos , o pliegues , modelo de recursión primitiva. cata
derriba un punto fijo capa por capa, utilizando una función de álgebra (o función de plegado ) para procesar cada capa. cata
requiere una instancia de Functor
para el tipo de plantilla 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
Desplegar una estructura de una capa a la vez
Los anamorfismos , o despliegues , modelan la primitiva corecursión. ana
construye un punto fijo capa por capa, utilizando una función de coalgebra (o función de despliegue ) para producir cada nueva capa. ana
requiere una instancia de Functor
para el tipo de plantilla 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
Tenga en cuenta que ana
y cata
son duales . Los tipos y las implementaciones son imágenes espejo de la otra.
Despliegue y luego plegado, fusionado.
Es común estructurar un programa para construir una estructura de datos y luego colapsarlo en un solo valor. Esto se llama un hilomorfismo o repliegue. Es posible elidir la estructura intermedia por completo para mejorar la eficiencia.
hylo :: Functor f => (a -> f a) -> (f b -> b) -> a -> b
hylo f g = g . fmap (hylo f g) . f -- no mention of Fix!
Derivación:
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
Recursion primitiva
Los paramorfismos modelan la recursión primitiva. En cada iteración del pliegue, la función de plegado recibe el subárbol para su posterior procesamiento.
para :: Functor f => (f (Fix f, a) -> a) -> Fix f -> a
para f = f . fmap (\x -> (x, para f x)) . unFix
Las tails
de Prelude se pueden modelar como 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 primitiva
Modelo de apomorfismos de la primitiva corecursión. En cada iteración del despliegue, la función de despliegue puede devolver una semilla nueva o un subárbol completo.
apo :: Functor f => (a -> f (Either (Fix f) a)) -> a -> Fix f
apo f = Fix . fmap (either id (apo f)) . f
Tenga en cuenta que apo
y para
son duales . Las flechas en el tipo se voltean; la tupla en para
es dual a la de Either
in apo
, y las implementaciones son imágenes espejo de la otra.