Que sont les paramorphismes?

En parcourant cet article classique , je suis bloqué sur les paramorphismes. Malheureusement, la section est assez mince et la page Wikipedia ne dit rien.

Ma traduction en haskell est:

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

Mais je ne le pense 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 les exemples utiles en action?


Oui, j’ai vu ces questions , mais elles ne couvrent pas directement les paramorphismes et ne signalent que des ressources pouvant servir de références, mais pas de matériel d’apprentissage.

Oui, c’est le para . Comparez avec catamorphisme ou foldr :

 para :: (a -> [a] -> b -> b) -> b -> [a] -> b foldr :: (a -> b -> b) -> b -> [a] -> b para cn (x : xs) = cx xs (para cn xs) foldr cn (x : xs) = cx (foldr cn xs) para cn [] = n foldr cn [] = n 

Certaines personnes appellent les paramorphismes “récursivité primitive” par opposition aux catamorphismes ( foldr ) étant “itération”.

Lorsque les deux parameters de foldr reçoivent une valeur calculée de manière récursive pour chaque sous-object récursif des données d’entrée (ici, c’est la queue de la liste), les parameters de para obtiennent à la fois le sous-object d’origine et la valeur calculée de manière récursive.

Un exemple de fonction qui est bien exprimé avec para est la collection des suffixes 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 plus simple est toujours

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

dans lequel la twig “cons” ignore son argument calculé récursivement et ne fait que rendre la queue. Évalué paresseusement, le calcul récursif ne se produit jamais et la queue est extraite à temps constant.

Vous pouvez définir foldr utilisant para assez facilement; c’est un peu plus compliqué de définir para partir de foldr , mais c’est certainement possible, et tout le monde devrait savoir comment ça se passe!

 foldr cn = para (\ x xs t -> cxt) n para cn = snd . foldr (\ x (xs, t) -> (x : xs, cx xs t)) ([], n) 

L’astuce pour définir para avec foldr consiste à reconstruire une copie des données d’origine, de manière à avoir access à une copie de la queue à chaque étape, même si nous n’avions pas access à l’original. À la fin, snd rejette 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 une expressivité pure, para ne vous donne rien de plus que foldr . Si vous utilisez cette version foldr -encoded de para , alors safeTail prendra du temps linéaire après tout, copiant l’élément tail par élément.

Donc, c’est tout: para est une version plus pratique de foldr qui vous donne un access immédiat à la fin de la liste ainsi que 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 sharepoint repère récursif d’un foncteur

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

tu as

 cata :: Functor f => (ft -> 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, les deux sont mutuellement définissables, avec para défini de cata par le même “faire une copie” astuce

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

Encore une fois, para n’est pas plus expressif que cata , mais plus pratique si vous avez besoin d’un access facile aux sous-structures de l’entrée.

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

Considérez les arbres de recherche binarys donnés par Fix TreeF

 data TreeF sub = Leaf | Node sub Integer sub 

et essayez de définir l’insertion pour les arbres de recherche binarys, d’abord en tant que cata , puis en tant que para . Vous trouverez la version para beaucoup plus facile, car à chaque nœud vous devrez insérer dans une sous-arborescence mais conserver l’autre tel qu’il était.