Zygomorphism是我们用来描述由两个半互递归函数构建的折叠的高深数学术语。我会举一个例子。
想象一个名为pm :: [Int] -> Int（代表加减）的函数，它通过在数字列表中交替插入+和-来实现，使得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(n2)。
我们可以注意到，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)
我们有一个fold（折叠）依赖于另一个fold的结果，并且我们能够将它们融合成列表的一次遍历。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 类似于 catamorphism 看到上一次迭代的答案，但是 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)
通过简单地忽略额外的参数，您可以从mutu中恢复出zygo。
zygoL 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实现。在foldology中，一切都与其他事物相关。
您可以从广义版本中恢复列表版本。
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
zygo和futu应该有什么类型签名吗？ - epsilonhalbezygoFix版本：zygo :: Functor f => (f b -> b) -> (f (a, b) -> a) -> Fix f -> a- haroldcarrfutuMu版本：futu :: (Mu b, Functor (PF b)) => Ann b -> (a -> F b (Futu b a)) -> a -> b（请参见 https://hackage.haskell.org/package/pointless-haskell-0.0.9/docs/Generics-Pointless-RecursionPatterns.html） - haroldcarr