Que sont les paramorphismes?

En lisant cet article classique , je suis coincé sur les paramorphismes. Malheureusement, la section est assez mince et la page Wikipédia ne dit rien.

Ma traduction Haskell est:

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

Mais je ne gémis pas - je n'ai aucune intuition pour la signature de type ou le résultat souhaité.

Qu'est-ce qu'un paramorphisme et quels sont quelques exemples utiles en action?

Oui, j'ai vu ces questions , mais elles ne couvrent pas directement les paramorphismes et ne désignent que des ressources qui peuvent être utiles comme références, mais pas comme supports d'apprentissage.

Oui c'est ça para. Comparez avec le catamorphisme, ou 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

Certaines personnes appellent les paramorphismes «récursion primitive» par opposition aux catamorphismes ( foldr) étant «itération».

Où foldrles deux paramètres reçoivent une valeur calculée de manière récursive pour chaque sous-objet récursif des données d'entrée (ici, c'est la queue de la liste), parales paramètres de s obtiennent à la fois le sous-objet d'origine et la valeur calculée de manière récursive à partir de celui-ci.

Un exemple de fonction qui est joliment exprimé avec paraest la collection des suffisants appropriés d'une liste.

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

pour que

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

Peut-être encore plus simple est-il

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

dans lequel la branche "cons" ignore son argument récursivement calculé et rend juste la queue. Evalué paresseusement, le calcul récursif ne se produit jamais et la queue est extraite en temps constant.

Vous pouvez définir en foldrutilisant paraassez facilement; il est un peu plus délicat à définir à parapartir foldr, mais il est certainement possible, et tout le monde devrait savoir comment faire!

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)

L'astuce pour définir paraavec foldrest de reconstruire une copie des données originales, de sorte que nous ayons accès à une copie de la queue à chaque étape, même si nous n'avions pas accès à l'original. À la fin, sndsupprime la copie de l'entrée et donne juste la valeur de sortie. Ce n'est pas très efficace, mais si vous êtes intéressé par l'expressivité pure, parane vous en donne pas plus foldr. Si vous utilisez cette foldrversion codée de para, safeTailcela prendra un temps linéaire après tout, la copie de la queue élément par élément.

Alors, c'est tout: parac'est une version plus pratique foldrqui vous donne un accès immédiat à la queue de la liste ainsi qu'à la valeur calculée à partir de celle-ci.

Dans le cas général, travailler avec un type de données généré comme point fixe récursif d'un foncteur

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

vous avez

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)

et encore une fois, les deux sont mutuellement définissables, avec paradéfinis à partir catade la même astuce "faire une copie"

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

Encore une fois, ce paran'est pas plus expressif que cata, mais plus pratique si vous avez besoin d'un accès facile aux sous-structures de l'entrée.

Edit: Je me suis souvenu d'un autre bel exemple.

Considérons les arbres de recherche binaires donnés par Fix TreeFoù

data TreeF sub = Leaf | Node sub Integer sub

et essayez de définir l'insertion pour les arbres de recherche binaires, d'abord comme a cata, puis comme a para. Vous trouverez la paraversion beaucoup plus facile, car à chaque nœud, vous devrez insérer dans un sous-arbre mais conserver l'autre tel qu'il était.