Zygomorphism是我们给从两个半相互递归函数构建的折叠起的高级数学名称。我举个例子。
想象一个函数pm :: [Int] -> Int（用于plus-minus），它穿插+并-交替穿过一个数字列表，例如pm [v,w,x,y,z] = v - (w + (x - (y + z))). 您可以使用原始递归将其写出来：
lengthEven :: [a] -> Bool
lengthEven = even . length
pm0 [] = 0
pm0 (x:xs) = if lengthEven xs
then x - pm0 xs
else x + pm0 xs
显然pm0不是组合- 您需要检查每个位置的整个列表的长度，以确定您是添加还是减去。当折叠函数需要在折叠的每次迭代中遍历整个子树时，Paramorphism对这种类型的原始递归进行建模。所以我们至少可以重写代码以符合既定模式。
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
但这是低效的。lengthEven在自拟态的每次迭代中遍历整个列表，从而产生 O(n 2 ) 算法。
我们可以通过注意到两者来取得进展，并且lengthEven可以para表示为具有...foldr
cataL = foldr
lengthEven' = cataL (\_ p -> not p) True
paraL' f z = snd . cataL (\x (xs, acc) -> (x:xs, f x xs acc)) ([], z)
...这表明我们可以将这两个操作融合到一个列表中。
pm2 = snd . cataL (\x (isEven, total) -> (not isEven, if isEven
then x - total
else x + total)) (True, 0)
我们有一个折叠取决于另一个折叠的结果，我们能够将它们融合到列表的一次遍历中。Zygomorphism 恰好捕捉到了这种模式。
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)
在折叠的每次迭代中，f从最后一次迭代中看到它的答案就像在变态中一样，但是g可以看到两个函数的答案。g与自己纠缠f。
我们将pm通过使用第一个折叠函数来计算列表的长度是偶数还是奇数，然后使用第二个折叠函数来计算总数，将其写成 zygomorphism。
pm3 = zygoL (\_ p -> not p) (\x isEven total -> if isEven
then x - total
else x + total) True 0
这是经典的函数式编程风格。我们有一个高阶函数来完成消耗列表的繁重工作；我们所要做的就是插入逻辑来聚合结果。构造显然终止（您只需要证明终止foldr），并且它比启动的原始手写版本更有效。
旁白： @AlexR在评论中指出 zygomorphism 有一个名为mutumorphism的大姐姐，它充分体现了相互递归的魅力。mutu概括zygo起来，两个折叠函数都可以检查另一个在上一次迭代中的结果。
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)
您只需忽略额外的参数即可
恢复zygo。mutuzygoL f = mutuL (\x p q -> f x p)
当然，所有这些折叠模式都从列表泛化到任意函子的固定点：
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))
比较 的定义zygo与的定义zygoL。还要注意zygo Fix = para，和那后三折而言可以实现cata。在折叠学中，一切都与其他一切有关。
您可以从通用版本恢复列表版本。
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