you - type of function haskell

Histomorfismos, zigomorfismos y Futumorphisms especializados en listas

Question

Terminé descifrándolo. Ver el video y las diapositivas de una charla que di:

• slides/pdf

• video

Pregunta original:

En mi esfuerzo por comprender los esquemas de recursión genéricos (es decir, que usan Fix ), he encontrado que es útil escribir versiones de solo listas de los diversos esquemas. Hace que sea mucho más fácil de entender los esquemas reales (sin la sobrecarga adicional de la Fix ).

Sin embargo, todavía no he descubierto cómo definir versiones de zygo y futu zygo para futu .

Aquí están mis definiciones especializadas hasta ahora:

cataL :: (a ->        b -> b) -> b -> [a] -> b
cataL f b (a : as) = f a    (cataL f b as)
cataL _ b []       = b

paraL :: (a -> [a] -> b -> b) -> b -> [a] -> b
paraL f b (a : as) = f a as (paraL f b as)
paraL _ b []       = b

-- TODO: histo

-- DONE: zygo (see below)

anaL  :: (b ->       (a, b))               -> b -> [a]
anaL  f b = let (a, b'') = f b in a : anaL f b''

anaL'' :: (b -> Maybe (a, b))               -> b -> [a]
anaL'' f b = case f b of
    Just (a, b'') -> a : anaL'' f b''
    Nothing      -> []

apoL :: ([b] -> Maybe (a, Either [b] [a])) -> [b] -> [a]
apoL f b = case f b of
    Nothing -> []
    Just (x, Left c)  -> x : apoL f c
    Just (x, Right e) -> x : e

-- DONE: futu (see below)

hyloL  :: (a -> c -> c) -> c -> (b -> Maybe (a, b)) -> b -> c
hyloL f z g = cataL f z . anaL'' g

hyloL'' :: (a -> c -> c) -> c -> (c -> Maybe (a, c))      -> c
hyloL'' f z g = case g z of
    Nothing     -> z
    Just (x,z'') -> f x (hyloL'' f z'' g)

¿Cómo se definen histo , zygo y futu para las listas?

Answer 1

Como nadie más ha respondido por futu todavía, intentaré futu a futu . Voy a usar ListF ab = Base [a] = ConsF ab | NilF ListF ab = Base [a] = ConsF ab | NilF

Tomando el tipo en recursion-schemes : futu :: Unfoldable t => (a -> Base t (Free (Base t) a)) -> a -> t .

Voy a ignorar la restricción Unfoldable y sustituir [b] por t .

(a -> Base [b] (Free (Base [b]) a)) -> a -> [b]
(a -> ListF b (Free (ListF b) a)) -> a -> [b]

Free (ListF b) a) es una lista, posiblemente con un agujero tipo-tipeado al final. Esto significa que es isomorfo a ([b], Maybe a) . Entonces ahora tenemos:

(a -> ListF b ([b], Maybe a)) -> a -> [b]

Eliminando el último ListF , notando que ListF ab es isomorfo a Maybe (a, b) :

(a -> Maybe (b, ([b], Maybe a))) -> a -> [b]

Ahora, estoy bastante seguro de que jugar type-tetris conduce a la única implementación sensata:

futuL f x = case f x of
  Nothing -> []
  Just (y, (ys, mz)) -> y : (ys ++ fz)
    where fz = case mz of
      Nothing -> []
      Just z -> futuL f z

Resumiendo la función resultante, futuL toma un valor inicial y una función que puede producir al menos un resultado, y posiblemente un nuevo valor inicial si produce un resultado.

Al principio pensé que esto era equivalente a

notFutuL :: (a -> ([b], Maybe a)) -> a -> [b]
notFutuL f x = case f x of
  (ys, mx) -> ys ++ case mx of
    Nothing -> []
    Just x'' -> notFutuL f x''

Y en la práctica, tal vez lo es, más o menos, pero la única diferencia significativa es que el futu real garantiza la productividad (es decir, si f siempre regresa, nunca estará atascado esperando para siempre el próximo elemento de lista).

Answer 2

El cigomorfismo es el nombre matemático de alto valor que le damos a los pliegues construidos a partir de dos funciones semi recursivas recursivas. Daré un ejemplo.

Imagine una función pm :: [Int] -> Int (para plus-minus ) que intercala + y - alternativamente a través de una lista de números, tal que pm [v,w,x,y,z] = v - (w + (x - (y + z))) . Puedes escribirlo usando la recursión primitiva:

lengthEven :: [a] -> Bool
lengthEven = even . length

pm0 [] = 0
pm0 (x:xs) = if lengthEven xs
             then x - pm0 xs
             else x + pm0 xs

Es evidente que pm0 no es compositional ; debe inspeccionar la longitud de toda la lista en cada posición para determinar si está agregando o quitando. El paramorfismo modela la recursión primitiva de este tipo, cuando la función de plegado necesita atravesar todo el subárbol en cada iteración del pliegue. Entonces, al menos, podemos reescribir el código para que se ajuste a un patrón establecido.

paraL :: (a -> [a] -> b -> b) -> b -> [a] -> b
paraL f z [] = z
paraL f z (x:xs) = f x xs (paraL f z xs)

pm1 = paraL (/x xs acc -> if lengthEven xs then x - acc else x + acc) 0

Pero esto es ineficiente. lengthEven atraviesa toda la lista en cada iteración del paramorfismo que resulta en un algoritmo O (n ² ).

Podemos avanzar notando que tanto lengthEven como para se pueden expresar como un catamorfismo con foldr ...

cataL = foldr

lengthEven'' = cataL (/_ p -> not p) True
paraL'' f z = snd . cataL (/x (xs, acc) -> (x:xs, f x xs acc)) ([], z)

... lo que sugiere que podamos fusionar las dos operaciones en un solo paso sobre la lista.

pm2 = snd . cataL (/x (isEven, total) -> (not isEven, if isEven
                                                      then x - total
                                                      else x + total)) (True, 0)

Tuvimos un doblez que dependía del resultado de otro doblez, y pudimos fusionarlos en un recorrido de la lista. El cigomorfismo capta exactamente este patrón.

zygoL :: (a -> b -> b) ->  -- a folding function
         (a -> b -> c -> c) ->  -- a folding function which depends on the result of the other fold
         b -> c ->  -- zeroes for the two folds
         [a] -> c
zygoL f g z e = snd . cataL (/x (p, q) -> (f x p, g x p q)) (z, e)

En cada iteración del pliegue, f ve su respuesta desde la última iteración como en un catamorfismo, pero g puede ver las respuestas de ambas funciones. g enreda con f .

Escribiremos pm como un cigomorfismo utilizando la primera función de plegado para contar si la lista es par o impar en longitud y la segunda para calcular el total.

pm3 = zygoL (/_ p -> not p) (/x isEven total -> if isEven
                                                then x - total
                                                else x + total) True 0

Este es el estilo de programación funcional clásico. Tenemos una función de orden superior haciendo el trabajo pesado de consumir la lista; todo lo que teníamos que hacer era conectar la lógica para agregar resultados. La construcción evidentemente termina (solo se necesita probar la finalización de foldr ), y es más eficiente que la versión original escrita a mano para arrancar.

Aparte : @AlexR señala en los comentarios que el cigomorfismo tiene una hermana mayor llamada mutumorismo , que captura la recursión mutua en todo su esplendor. mutu generaliza zygo en que ambas funciones de plegado pueden inspeccionar el resultado del otro desde la iteración anterior.

mutuL :: (a -> b -> c -> b) ->
         (a -> b -> c -> c) ->
         b -> c ->
         [a] -> c
mutuL f g z e = snd . cataL (/x (p, q) -> (f x p q, g x p q)) (z, e)

Recuperas zygo de mutu simplemente ignorando el argumento extra. zygoL f = mutuL (/xpq -> fxp)

Por supuesto, todos estos patrones de plegado se generalizan desde las listas hasta el punto fijo de un functor arbitrario:

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

cata :: Functor f => (f a -> a) -> Fix f -> a
cata f = f . fmap (cata f) . unFix

para :: Functor f => (f (Fix f, a) -> a) -> Fix f -> a
para f = snd . cata (/x -> (Fix $ fmap fst x, f x))

zygo :: Functor f => (f b -> b) -> (f (b, a) -> a) -> Fix f -> a
zygo f g = snd . cata (/x -> (f $ fmap fst x, g x))

mutu :: Functor f => (f (b, a) -> b) -> (f (b, a) -> a) -> Fix f -> a
mutu f g = snd . cata (/x -> (f x, g x))

Compare la definición de zygo con la de zygoL . También tenga en cuenta que zygo Fix = para , y que los últimos tres pliegues se pueden implementar en términos de cata . En foldology todo está relacionado con todo lo demás.

Puede recuperar la versión de la lista de la versión generalizada.

data ListF a r = Nil_ | Cons_ a r deriving Functor
type List a = Fix (ListF a)

zygoL'' :: (a -> b -> b) -> (a -> b -> c -> c) -> b -> c -> List a -> c
zygoL'' f g z e = zygo k l
    where k Nil_ = z
          k (Cons_ x y) = f x y
          l Nil_ = e
          l (Cons_ x (y, z)) = g x y z

pm4 = zygoL'' (/_ p -> not p) (/x isEven total -> if isEven
                                                 then x - total
                                                 else x + total) True 0

Answer 3

El histomorfismo modela la programación dinámica , la técnica de tabular los resultados de subcomputaciones previas. (A veces se denomina inducción de curso de valor ). En un histomorfismo, la función de plegado tiene acceso a una tabla de los resultados de iteraciones anteriores del pliegue. Compare esto con el catamorfismo, donde la función de plegado solo puede ver el resultado de la última iteración. El histomorfismo tiene el beneficio de la retrospectiva: puedes ver toda la historia.

Aquí está la idea. A medida que consumamos la lista de entrada, el álgebra plegable emitirá una secuencia de b s. histo anotará cada b medida que emerge, uniéndolo a la tabla de resultados. La cantidad de elementos en el historial es igual a la cantidad de capas de lista que ha procesado; para cuando haya eliminado toda la lista, el historial de su operación tendrá una longitud igual a la de la lista.

Este es el aspecto de la historia de la iteración de una lista (ory):

data History a b = Ancient b | Age a b (History a b)

History es una lista de pares de cosas y resultados, con un resultado adicional al final correspondiente a [] -thing. Emparejaremos cada capa de la lista de entrada con su resultado correspondiente.

cataL = foldr

history :: (a -> History a b -> b) -> b -> [a] -> History a b
history f z = cataL (/x h -> Age x (f x h) h) (Ancient z)

Una vez que haya doblado la lista completa de derecha a izquierda, su resultado final estará en la parte superior de la pila.

headH :: History a b -> b
headH (Ancient x) = x
headH (Age _ x _) = x

histoL :: (a -> History a b -> b) -> b -> [a] -> b
histoL f z = headH . history f z

(Sucede que History a es comonad , pero headH (née extract ) es todo lo que necesitamos para definir histoL .)

History etiqueta cada capa de la lista de entrada con su resultado correspondiente. La comonad de cofre captura el patrón de etiquetado de cada capa de una estructura arbitraria.

data Cofree f a = Cofree { headC :: a, tailC :: f (Cofree f a) }

(Se me ocurrió la History al conectar ListF en Cofree y simplificar).

Compare esto con la mónada libre ,

data Free f a = Free (f (Free f a))
              | Return a

Free es un tipo de coproducto; Cofree es un tipo de producto. Capas Free hasta una lasaña de f s, con valores a en la parte inferior de la lasaña. Cofree capas de la lasaña con valores a en cada capa. Las mónadas libres son árboles generalizados etiquetados externamente; cofre comonads son árboles generalizados etiquetados internamente.

Con Cofree en mano, podemos generalizar desde listas hasta el punto fijo de un funtor arbitrario,

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

cata :: Functor f => (f b -> b) -> Fix f -> b
cata f = f . fmap (cata f) . unFix

histo :: Functor f => (f (Cofree f b) -> b) -> Fix f -> b
histo f = headC . cata (/x -> Cofree (f x) x)

y una vez más recuperar la versión de la lista.

data ListF a r = Nil_ | Cons_ a r deriving Functor
type List a = Fix (ListF a)
type History'' a b = Cofree (ListF a) b

histoL'' :: (a -> History'' a b -> b) -> b -> List a -> b
histoL'' f z = histo g
    where g Nil_ = z
          g (Cons_ x h) = f x h

Aparte : histo es el dual de futu . Mira sus tipos.

histo :: Functor f => (f (Cofree f a) -> a) -> (Fix f -> a)
futu  :: Functor f => (a  ->  f (Free f a)) -> (a -> Fix f)

futu es histo con las flechas volteadas y con Free reemplazado por Cofree . Los histomorfismos ven el pasado; futumorphisms predicen el futuro. Y muy parecido a cata f . ana g cata f . ana g puede fusionarse en un hylomorphism , histo f . futu g histo f . futu g puede fusionarse en un chronomorphism .

Incluso si omite las partes de matemáticas, este documento de Hinze y Wu presenta un buen tutorial basado en ejemplos sobre histomorfismos y su uso.