Zygomorphism est de la haute-falutin' mathsy nom que nous donnons à plis construite à partir de deux semi-mutuellement des fonctions récursives. Je vais vous donner un exemple.
Imaginez une fonction pm :: [Int] -> Int (pour les plus-moins) qui intersperses + et - en alternance par le biais d'une liste de nombres, tels que pm [v,w,x,y,z] = v - (w + (x - (y + z))). Vous pouvez l'écrire à l'aide de primitives de récursivité:
lengthEven :: [a] -> Bool
lengthEven = even . length
pm0 [] = 0
pm0 (x:xs) = if lengthEven xs
then x - pm0 xs
else x + pm0 xs
Clairement pm0 n'est pas de la composition - , vous devez vérifier la longueur de l'ensemble de la liste à chaque position pour déterminer si vous êtes l'ajout ou la soustraction. Paramorphism modèles de la récursion primitive de ce genre, lorsque la fonction de pliage doit parcourir l'ensemble de la sous-arborescence à chaque itération de la pliure. Si au moins nous pouvons réécrire le code pour être conforme à un modèle établi.
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
Mais c'est inefficace. lengthEven traverse toute la liste à chaque itération de la paramorphism résultant en un temps O(n2) de l'algorithme.
Nous pouvons faire des progrès en notant que les deux lengthEven et para peut être exprimée comme une catamorphism avec foldr...
cataL = foldr
lengthEven' = cataL (\_ p -> not p) True
paraL' f z = snd . cataL (\x (xs, acc) -> (x:xs, f x xs acc)) ([], z)
... ce qui suggère que nous pourrions être en mesure de fusionner les deux opérations en un seul passage sur la liste.
pm2 = snd . cataL (\x (isEven, total) -> (not isEven, if isEven
then x - total
else x + total)) (True, 0)
Nous avons eu un pli qui dépendait du résultat de l'autre fois, et nous avons été en mesure de les faire fusionner en un seul parcours de la liste. Zygomorphism capture exactement ce modèle.
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)
À chaque itération de la bergerie, f voit sa réponse à partir de la dernière itération comme dans un catamorphism, mais g arrive à voir à la fois les fonctions de réponses. g entangles lui-même avec f.
Nous allons écrire pm comme un zygomorphism par l'aide de la première fonction de pliage à compter de savoir si la liste est pair ou impair dans la longueur et la seconde pour calculer le total.
pm3 = zygoL (\_ p -> not p) (\x isEven total -> if isEven
then x - total
else x + total) True 0
C'est classique de la programmation fonctionnelle style. Nous avons un ordre supérieur de la fonction de faire de levage lourds de la consommation de la liste; tout ce que nous avions à faire était prise dans la logique de l'ensemble des résultats. La construction de toute évidence se termine (vous avez seulement besoin de prouver la terminaison pour foldr), et il est plus efficace que l'original, écrit à la main la version de boot.
De côté: @AlexR points dans les commentaires que zygomorphism a une grande soeur nommée mutumorphism, qui capte la récursivité mutuelle dans toutes les
sa gloire. mutu généralise zygo dans les deux le pliage
les fonctions sont autorisés à inspecter les autres à la suite de la précédente
itération.
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)
Vous récupérez zygo de mutu simplement en ignorant l'argument supplémentaire.
zygoL f = mutuL (\x p q -> f x p)
Bien sûr, tous ces modèles de pliage de généraliser à partir de listes à la fixpoint de l'arbitraire d'un foncteur:
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))
Comparer la définition de l' zygo avec zygoL. Notez aussi que l' zygo Fix = para, et que les trois derniers plis peuvent être mis en œuvre en termes de cata. Dans foldology tout est lié à tout le reste.
Vous pouvez récupérer la version de liste à partir de la version généralisée.
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
