Quels sont les paramorphisms ?

Question

La lecture par le biais de ce classique sur le papier, je suis bloqué sur paramorphisms. Malheureusement, l'article est assez mince, et la page de Wikipedia ne veut rien dire.

Mon Haskell traduction 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 connaît pas que -- je n'ai pas d'intuition pour le type de signature ou le résultat souhaité.

Qu'est ce qu'un paramorphism, et ce sont quelques exemples utiles dans l'action?

---

Oui, j'ai vu ces questions, mais elles ne couvrent pas paramorphisms directement et uniquement les ressources qui peuvent être utiles comme références, mais pas que du matériel d'apprentissage.

Answer 1

Oui, c'est para. Comparer avec catamorphism, 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 paramorphisms "récursion primitive" par contraste avec catamorphisms (foldr) d'être "itération".

Où foldr's deux paramètres sont donnés d'une manière récursive valeur calculée pour chaque récursive des sous-objet de la saisie de données (ici, c'est la queue de la liste, paras'paramètres d'obtenir à la fois l'original sous-objet et la valeur calculée de manière récursive.

Un exemple de fonction qui est joliment exprimé avec para de la collecte de la bonne suffit d'une liste.

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

de sorte que

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

Probablement plus simple est encore d'

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

dans lequel les "contre" de la branche ignore sa manière récursive calculée argument et donne juste en arrière de la queue. Évalué paresseusement, le récursive de calcul n'arrive jamais, et la queue est extrait en temps constant.

Vous pouvez définir foldr l'aide para assez facilement; il est un peu plus délicat à définir para de foldr, mais c'est certainement possible, et tout le monde devrait savoir comment c'est fait!

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)

Le truc à la définition d' para avec foldr est de reconstituer une copie des données d'origine, de sorte que nous avons accès à une copie de la queue à chaque étape, même si nous n'avions pas accès à l'original. À la fin, snd les rejets de la copie de l'entrée et vous donne juste la valeur de sortie. Ce n'est pas très efficace, mais si vous êtes intéressé dans la pure expressivité, para vous donne pas plus de foldr. Si vous utilisez cette foldr-version codée d' para, alors safeTail prendra le temps linéaire après tout, la copie de la queue de l'élément par élément.

Donc, c'est: para est plus pratique pour version d' foldr qui vous donne un accès immédiat à la queue de la liste ainsi que la valeur calculée à partir d'elle.

Dans le cas général, travailler avec un type de données générée par la récursif fixpoint 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éfinissable, avec para défini à partir d' cata par le même "créer une copie" truc

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 accès facile aux infrastructures de l'entrée.

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

Envisager de binaires de recherche arbres donné par Fix TreeF où

data TreeF sub = Leaf | Node sub Integer sub

et essayer de définir d'insertion pour les arbres binaires, d'abord en tant que cata, puis en tant que para. Vous trouverez l' para version beaucoup plus facile, comme à chaque nœud, vous aurez besoin de les insérer dans un sous-arbre, mais de préserver l'autre comme il est.