Fix 和 Mu 同构
Fix and Mu isomorphic
在 recursion-schemes 包中定义了以下类型：
newtype Fix f = Fix (f (Fix f))
newtype Mu f = Mu (forall a. (f a -> a) -> a)
它们是同构的吗？如果是，你如何证明？
Are they isomorphic?
是的，它们在Haskell中是同构的。有关一些附加说明，请参阅 。
If so, how do you prove it?
让我们从定义执行转换的函数开始：
muToFix :: Mu f -> Fix f
muToFix (Mu s) = s Fix
fixToMu :: Functor f => Fix f -> Mu f
fixToMu t = Mu (\alg -> cata alg t)
为了证明这些函数见证同构，我们必须证明：
muToFix . fixToMu = id
fixToMu . muToFix = id
从 Fix 返回
同构的一个方向比另一个更直接：
muToFix (fixToMu t) = t
muToFix (fixToMu t) -- LHS
muToFix (Mu (\f -> cata f t))
(\f -> cata f t) Fix
cata Fix t -- See below.
t -- LHS = RHS
上面最后一段，cata Fix t = t，可以通过cata的定义来验证：
cata :: Functor f => (f a -> a) -> Fix f -> a
cata alg = alg . fmap (cata alg) . unfix
cata Fix t，那么，就是Fix (fmap (cata Fix) (unfix t))。我们可以使用归纳法来证明它必须是 t，至少对于有限的 t 而言（无限结构变得更加微妙——请参阅本答案末尾的附录）。有两种可能需要考虑：
unfix t :: f (Fix f) 是空的，没有可挖掘的递归位置。在那种情况下，对于某些 z :: f Void，它必须等于 fmap absurd z，因此：
cata Fix t
Fix (fmap (cata Fix) (unfix t))
Fix (fmap (cata Fix) (fmap absurd z))
Fix (fmap (cata Fix . absurd) z)
-- fmap doesn't do anything on an empty structure.
Fix (fmap absurd z)
Fix (unfix t)
t
unfix t 不为空。在那种情况下，我们至少知道 fmap (cata Fix) 除了在递归位置上应用 cata Fix 之外不能做任何事情。这里的归纳假设是这样做会使那些位置保持不变。然后我们有：
cata Fix t
Fix (fmap (cata Fix) (unfix t))
Fix (unfix t) -- Induction hypothesis.
t
（最终，cata Fix = id 是 Fix :: f (Fix f) -> Fix x 作为初始 F 代数的推论。直接求助于该事实
在这个证明的上下文中可能会太捷径了。）
从 Mu 返回
给定 muToFix . fixToMu = id，要证明 fixToMu . muToFix = id 只需证明：
那muToFix是单射的，或者
那个fixToMu是满射的。
让我们选择第二个选项，并查看相关定义：
newtype Mu f = Mu (forall a. (f a -> a) -> a)
fixToMu :: Functor f => Fix f -> Mu f
fixToMu t = Mu (\alg -> cata alg t)
fixToMu 是满射，那么，意味着给定任何特定的 Functor f，所有 forall a. (f a -> a) -> a 类型的函数都可以定义为 \alg -> cata alg t ，对于某些特定的 t :: Fix f。然后，任务变成了对 forall a. (f a -> a) -> a 函数进行编目，并查看是否所有函数都可以用该形式表示。
我们如何在不依赖 fixToMu 的情况下定义 forall a. (f a -> a) -> a 函数？无论如何，它必须涉及使用作为参数提供的 f a -> a 代数来获得 a 结果。直接途径是将其应用于某些 f a 值。一个主要的警告是，由于 a 是多态的，我们必须能够为 a 的任何选择联想到所说的 f a 值。只要 f-values 恰好存在，这就是一个可行的策略。在这种情况下，我们可以这样做：
fromEmpty :: Functor f => f Void -> forall a. (f a -> a) -> a
fromEmpty z = \alg -> alg (fmap absurd z)
为了使符号更清晰，让我们为可用于定义 forall a. (f a -> a) -> a 函数的事物定义一个类型：
data Moo f = Empty (f Void)
fromMoo :: Functor f => Moo f -> forall a. (f a -> a) -> a
fromMoo (Empty z) = \alg -> alg (fmap absurd z)
除了直达路线，还有另外一种可能。鉴于 f 是一个 Functor，如果我们有一个 f (Moo f) 值，我们可以应用代数两次，第一次应用在外部 f 层下，通过 fmap 和 fromMoo:
fromLayered :: Functor f => f (Moo f) -> forall a. (f a -> a) -> a
fromLayered u = \alg -> alg (fmap (\moo -> fromMoo moo alg) u)
考虑到我们也可以从 f (Moo f) 值中得到 forall a. (f a -> a) -> a，将它们添加为 Moo:
是有意义的
data Moo f = Empty (f Void) | Layered (f (Moo f))
因此，fromLayered 可以合并到 fromMoo:
fromMoo :: Functor f => Moo f -> forall a. (f a -> a) -> a
fromMoo = \case
Empty z -> \alg -> alg (fmap absurd z)
Layered u -> \alg -> alg (fmap (\moo -> fromMoo moo alg) u)
请注意，通过这样做，我们偷偷地从在一个 f 层下应用 alg 转移到在任意数量的 f 层下递归应用 alg .
接下来，我们可以注意到可以将 f Void 值注入到 Layered 构造函数中：
emptyLayered :: Functor f => f Void -> Moo f
emptyLayered z = Layered (fmap absurd z)
这意味着我们实际上不需要 Empty 构造函数：
newtype Moo f = Moo (f (Moo f))
unMoo :: Moo f -> f (Moo f)
unMoo (Moo u) = u
fromMoo 中的 Empty 案例呢？这两种情况的唯一区别是，在 Empty 的情况下，我们有 absurd 而不是 \moo -> fromMoo moo alg。由于所有 Void -> a 函数都是 absurd，我们也不需要单独的 Empty 案例：
fromMoo :: Functor f => Moo f -> forall a. (f a -> a) -> a
fromMoo (Moo u) = \alg -> alg (fmap (\moo -> fromMoo moo alg) u)
一个可能的修饰调整是翻转 fromMoo 参数，这样我们就不需要将 fmap 的参数写成 lambda：
foldMoo :: Functor f => (f a -> a) -> Moo f -> a
foldMoo alg (Moo u) = alg (fmap (foldMoo alg) u)
或者，更多点免费：
foldMoo :: Functor f => (f a -> a) -> Moo f -> a
foldMoo alg = alg . fmap (foldMoo alg) . unMoo
此时，再次查看我们的定义表明需要进行一些重命名：
newtype Fix f = Fix (f (Fix f))
unfix :: Fix f -> f (Fix f)
unfix (Fix u) = u
cata :: Functor f => (f a -> a) -> Fix f -> a
cata alg = alg . fmap (cata alg) . unfix
fromFix :: Functor f => Fix f -> forall a. (f a -> a) -> a
fromFix t = \alg -> cata alg t
就是这样：对于某些 t :: Fix f，所有 forall a. (f a -> a) -> a 函数都具有 \alg -> cata alg t 的形式。因此，fixToMu 是满射，我们得到了想要的同构。
附录
在评论中，提出了一个关于归纳论证在 cata Fix t = t 推导中的适用性的相关问题。至少，函子定律和参数性确保 fmap (cata Fix) 不会产生额外的工作（例如，它不会扩大结构，或引入额外的递归位置来挖掘），这证明了为什么要进入递归位置在推导的归纳步骤中很重要。既然如此，如果t是一个有限结构，最终会达到空f (Fix t)的基本情况，一切都清楚了。但是，如果我们允许 t 是无限的，我们就可以不断下降，在 fmap 之后 fmap 在 fmap 之后，永远不会达到基本情况。
不过，无限结构的情况并不像乍看起来那么糟糕。惰性，这首先使无限结构可行，使我们能够懒惰地使用无限结构：
GHCi> :info ListF
data ListF a b = Nil | Cons a b
-- etc.
GHCi> ones = Fix (Cons 1 ones)
GHCi> (\(Fix (Cons a _)) -> a) (cata Fix ones)
1
GHCi> (\(Fix (Cons _ (Fix (Cons a _)))) -> a) (cata Fix ones)
1
虽然递归位置的连续性无限延伸，但我们可以在任何一点停止并从周围的 ListF 函子上下文中获得有用的结果。需要重复的是，这样的上下文不受 fmap 的影响，因此我们可能使用的结构的任何有限部分都不会受到 cata Fix.
的影响
如本次讨论的其他地方所述，这种惰性缓解反映了惰性如何破坏固定点 Mu、Fix 和 Nu 之间的区别。没有惰性，Fix 不足以编码有效的 corecursion，因此我们必须切换到最大不动点 Nu。这是差异的一个小例子：
GHCi> :set -XBangPatterns
GHCi> -- Like ListF, but strict in the recursive position.
GHCi> data SListF a b = SNil | SCons a !b deriving Functor
GHCi> ones = Nu (\() -> SCons 1 ()) ()
GHCi> (\(Nu c a) -> (\(SCons a _) -> a) (c a)) ones
1
GHCi> ones' = Fix (SCons 1 ones')
GHCi> (\(Fix (SCons a _)) -> a) ones'
^CInterrupted.
在 recursion-schemes 包中定义了以下类型：
newtype Fix f = Fix (f (Fix f))
newtype Mu f = Mu (forall a. (f a -> a) -> a)
它们是同构的吗？如果是，你如何证明？
Are they isomorphic?
是的，它们在Haskell中是同构的。有关一些附加说明，请参阅
If so, how do you prove it?
让我们从定义执行转换的函数开始：
muToFix :: Mu f -> Fix f
muToFix (Mu s) = s Fix
fixToMu :: Functor f => Fix f -> Mu f
fixToMu t = Mu (\alg -> cata alg t)
为了证明这些函数见证同构，我们必须证明：
muToFix . fixToMu = id
fixToMu . muToFix = id
从 Fix 返回
同构的一个方向比另一个更直接：
muToFix (fixToMu t) = t
muToFix (fixToMu t) -- LHS
muToFix (Mu (\f -> cata f t))
(\f -> cata f t) Fix
cata Fix t -- See below.
t -- LHS = RHS
上面最后一段，cata Fix t = t，可以通过cata的定义来验证：
cata :: Functor f => (f a -> a) -> Fix f -> a
cata alg = alg . fmap (cata alg) . unfix
cata Fix t，那么，就是Fix (fmap (cata Fix) (unfix t))。我们可以使用归纳法来证明它必须是 t，至少对于有限的 t 而言（无限结构变得更加微妙——请参阅本答案末尾的附录）。有两种可能需要考虑：
unfix t :: f (Fix f)是空的，没有可挖掘的递归位置。在那种情况下，对于某些z :: f Void，它必须等于fmap absurd z，因此：cata Fix t Fix (fmap (cata Fix) (unfix t)) Fix (fmap (cata Fix) (fmap absurd z)) Fix (fmap (cata Fix . absurd) z) -- fmap doesn't do anything on an empty structure. Fix (fmap absurd z) Fix (unfix t) tunfix t不为空。在那种情况下，我们至少知道fmap (cata Fix)除了在递归位置上应用cata Fix之外不能做任何事情。这里的归纳假设是这样做会使那些位置保持不变。然后我们有：cata Fix t Fix (fmap (cata Fix) (unfix t)) Fix (unfix t) -- Induction hypothesis. t
（最终，cata Fix = id 是 Fix :: f (Fix f) -> Fix x 作为初始 F 代数的推论。直接求助于该事实
在这个证明的上下文中可能会太捷径了。）
从 Mu 返回
给定 muToFix . fixToMu = id，要证明 fixToMu . muToFix = id 只需证明：
那
muToFix是单射的，或者那个
fixToMu是满射的。
让我们选择第二个选项，并查看相关定义：
newtype Mu f = Mu (forall a. (f a -> a) -> a)
fixToMu :: Functor f => Fix f -> Mu f
fixToMu t = Mu (\alg -> cata alg t)
fixToMu 是满射，那么，意味着给定任何特定的 Functor f，所有 forall a. (f a -> a) -> a 类型的函数都可以定义为 \alg -> cata alg t ，对于某些特定的 t :: Fix f。然后，任务变成了对 forall a. (f a -> a) -> a 函数进行编目，并查看是否所有函数都可以用该形式表示。
我们如何在不依赖 fixToMu 的情况下定义 forall a. (f a -> a) -> a 函数？无论如何，它必须涉及使用作为参数提供的 f a -> a 代数来获得 a 结果。直接途径是将其应用于某些 f a 值。一个主要的警告是，由于 a 是多态的，我们必须能够为 a 的任何选择联想到所说的 f a 值。只要 f-values 恰好存在，这就是一个可行的策略。在这种情况下，我们可以这样做：
fromEmpty :: Functor f => f Void -> forall a. (f a -> a) -> a
fromEmpty z = \alg -> alg (fmap absurd z)
为了使符号更清晰，让我们为可用于定义 forall a. (f a -> a) -> a 函数的事物定义一个类型：
data Moo f = Empty (f Void)
fromMoo :: Functor f => Moo f -> forall a. (f a -> a) -> a
fromMoo (Empty z) = \alg -> alg (fmap absurd z)
除了直达路线，还有另外一种可能。鉴于 f 是一个 Functor，如果我们有一个 f (Moo f) 值，我们可以应用代数两次，第一次应用在外部 f 层下，通过 fmap 和 fromMoo:
fromLayered :: Functor f => f (Moo f) -> forall a. (f a -> a) -> a
fromLayered u = \alg -> alg (fmap (\moo -> fromMoo moo alg) u)
考虑到我们也可以从 f (Moo f) 值中得到 forall a. (f a -> a) -> a，将它们添加为 Moo:
data Moo f = Empty (f Void) | Layered (f (Moo f))
因此，fromLayered 可以合并到 fromMoo:
fromMoo :: Functor f => Moo f -> forall a. (f a -> a) -> a
fromMoo = \case
Empty z -> \alg -> alg (fmap absurd z)
Layered u -> \alg -> alg (fmap (\moo -> fromMoo moo alg) u)
请注意，通过这样做，我们偷偷地从在一个 f 层下应用 alg 转移到在任意数量的 f 层下递归应用 alg .
接下来，我们可以注意到可以将 f Void 值注入到 Layered 构造函数中：
emptyLayered :: Functor f => f Void -> Moo f
emptyLayered z = Layered (fmap absurd z)
这意味着我们实际上不需要 Empty 构造函数：
newtype Moo f = Moo (f (Moo f))
unMoo :: Moo f -> f (Moo f)
unMoo (Moo u) = u
fromMoo 中的 Empty 案例呢？这两种情况的唯一区别是，在 Empty 的情况下，我们有 absurd 而不是 \moo -> fromMoo moo alg。由于所有 Void -> a 函数都是 absurd，我们也不需要单独的 Empty 案例：
fromMoo :: Functor f => Moo f -> forall a. (f a -> a) -> a
fromMoo (Moo u) = \alg -> alg (fmap (\moo -> fromMoo moo alg) u)
一个可能的修饰调整是翻转 fromMoo 参数，这样我们就不需要将 fmap 的参数写成 lambda：
foldMoo :: Functor f => (f a -> a) -> Moo f -> a
foldMoo alg (Moo u) = alg (fmap (foldMoo alg) u)
或者，更多点免费：
foldMoo :: Functor f => (f a -> a) -> Moo f -> a
foldMoo alg = alg . fmap (foldMoo alg) . unMoo
此时，再次查看我们的定义表明需要进行一些重命名：
newtype Fix f = Fix (f (Fix f))
unfix :: Fix f -> f (Fix f)
unfix (Fix u) = u
cata :: Functor f => (f a -> a) -> Fix f -> a
cata alg = alg . fmap (cata alg) . unfix
fromFix :: Functor f => Fix f -> forall a. (f a -> a) -> a
fromFix t = \alg -> cata alg t
就是这样：对于某些 t :: Fix f，所有 forall a. (f a -> a) -> a 函数都具有 \alg -> cata alg t 的形式。因此，fixToMu 是满射，我们得到了想要的同构。
附录
在评论中，提出了一个关于归纳论证在 cata Fix t = t 推导中的适用性的相关问题。至少，函子定律和参数性确保 fmap (cata Fix) 不会产生额外的工作（例如，它不会扩大结构，或引入额外的递归位置来挖掘），这证明了为什么要进入递归位置在推导的归纳步骤中很重要。既然如此，如果t是一个有限结构，最终会达到空f (Fix t)的基本情况，一切都清楚了。但是，如果我们允许 t 是无限的，我们就可以不断下降，在 fmap 之后 fmap 在 fmap 之后，永远不会达到基本情况。
不过，无限结构的情况并不像乍看起来那么糟糕。惰性，这首先使无限结构可行，使我们能够懒惰地使用无限结构：
GHCi> :info ListF
data ListF a b = Nil | Cons a b
-- etc.
GHCi> ones = Fix (Cons 1 ones)
GHCi> (\(Fix (Cons a _)) -> a) (cata Fix ones)
1
GHCi> (\(Fix (Cons _ (Fix (Cons a _)))) -> a) (cata Fix ones)
1
虽然递归位置的连续性无限延伸，但我们可以在任何一点停止并从周围的 ListF 函子上下文中获得有用的结果。需要重复的是，这样的上下文不受 fmap 的影响，因此我们可能使用的结构的任何有限部分都不会受到 cata Fix.
如本次讨论的其他地方所述，这种惰性缓解反映了惰性如何破坏固定点 Mu、Fix 和 Nu 之间的区别。没有惰性，Fix 不足以编码有效的 corecursion，因此我们必须切换到最大不动点 Nu。这是差异的一个小例子：
GHCi> :set -XBangPatterns
GHCi> -- Like ListF, but strict in the recursive position.
GHCi> data SListF a b = SNil | SCons a !b deriving Functor
GHCi> ones = Nu (\() -> SCons 1 ()) ()
GHCi> (\(Nu c a) -> (\(SCons a _) -> a) (c a)) ones
1
GHCi> ones' = Fix (SCons 1 ones')
GHCi> (\(Fix (SCons a _)) -> a) ones'
^CInterrupted.