haskell - meta tags ejemplos

¿Qué son los paramorfismos?

Question

Al leer este artículo clásico , estoy atascado en paramorfismos. Lamentablemente, la sección es bastante delgada, y la página de Wikipedia no dice nada.

Mi traducción de Haskell es:

para :: (a -> [a] -> b -> b) -> b -> [a] -> b
para f base = h
  where
    h []       =   base
    h (x:xs)   =   f x xs (h xs)

Pero no entiendo eso: no tengo ninguna intuición para la firma del tipo o el resultado deseado.

¿Qué es un paramorfismo y cuáles son algunos ejemplos útiles en acción?

Sí, he visto these questions , pero no cubren los paramorfismos directamente y solo apuntan a resources que pueden ser útiles como referencias, pero no como materiales de aprendizaje.

Answer 1

Sí, eso es para . Comparar con catamorfismo o foldr :

para  :: (a -> [a] -> b -> b) -> b -> [a] -> b
foldr :: (a ->        b -> b) -> b -> [a] -> b

para  c n (x : xs) = c x xs (para c n xs)
foldr c n (x : xs) = c x    (foldr c n xs)
para  c n []       = n
foldr c n []       = n

Algunas personas llaman a los paramorfismos "recursión primitiva" en contraste con los catamorfismos ( foldr ) que son "iteración".

Cuando los dos parámetros de foldr reciben un valor calculado recursivamente para cada subobjeto recursivo de los datos de entrada (aquí, esa es la cola de la lista), los parámetros de para obtienen tanto el subobjeto original como el valor calculado recursivamente a partir de él.

Una función de ejemplo que se expresa muy bien con para es la recopilación de los sufijos adecuados de una lista.

suff :: [x] -> [[x]]
suff = para (/ x xs suffxs -> xs : suffxs) []

así que eso

suff "suffix" = ["uffix", "ffix", "fix", "ix", "x", ""]

Posiblemente aún más simple es

safeTail :: [x] -> Maybe [x]
safeTail = para (/ _ xs _ -> Just xs) Nothing

en el cual la rama "contras" ignora su argumento recursivamente calculado y simplemente devuelve la cola. Evaluado perezosamente, el cálculo recursivo nunca ocurre y la cola se extrae en tiempo constante.

Puede definir foldr usando para bastante fácilmente; es un poco más complicado definir para from foldr , pero ciertamente es posible, ¡y todos deberían saber cómo se hace!

foldr c n =       para  (/ x  xs  t ->           c x    t)       n
para  c n = snd . foldr (/ x (xs, t) -> (x : xs, c x xs t)) ([], n)

El truco para definir para con foldr es reconstruir una copia de los datos originales, de modo que tengamos acceso a una copia de la cola en cada paso, aunque no hayamos tenido acceso al original. Al final, snd descarta la copia de la entrada y le da solo el valor de salida. No es muy eficiente, pero si estás interesado en la pura expresividad, para no te da más que foldr . Si utiliza esta versión foldr foldr de para , entonces safeTail llevará tiempo lineal después de todo, copiando el elemento de cola por elemento.

Entonces, eso es todo: para es una versión más conveniente de foldr que le da acceso inmediato a la cola de la lista, así como también al valor calculado a partir de ella.

En el caso general, trabajar con un tipo de datos generado como el punto fijo recursivo de un functor

data Fix f = In (f (Fix f))

tienes

cata :: Functor f => (f         t  -> t) -> Fix f -> t
para :: Functor f => (f (Fix f, t) -> t) -> Fix f -> t

cata phi (In ff) = phi (fmap (cata phi) ff)
para psi (In ff) = psi (fmap keepCopy   ff) where
  keepCopy x = (x, para psi x)

y de nuevo, los dos son mutuamente definibles, con un para definido de cata por el mismo truco de "hacer una copia"

para psi = snd . cata (/ fxt -> (In (fmap fst fxt), psi fxt))

De nuevo, para no es más expresivo que cata , pero es más conveniente si necesita un acceso fácil a las subestructuras de la entrada.

Editar: recordé otro buen ejemplo.

Considere los árboles de búsqueda binarios proporcionados por Fix TreeF donde

data TreeF sub = Leaf | Node sub Integer sub

e intente definir la inserción para los árboles de búsqueda binarios, primero como una cata , luego como un para . Encontrarás la versión para mucho más fácil, ya que en cada nodo necesitarás insertar en un subárbol pero preservar el otro como estaba.