haskell - Ed Kmett的递归方案包中的Fix，Mu和Nu有什么区别

在Ed Kmett的recursion-scheme包中，有三个声明:

newtype Fix f = Fix (f (Fix f))

newtype Mu f = Mu (forall a. (f a -> a) -> a)

data Nu f where
  Nu :: (a -> f a) -> a -> Nu f

这三种数据类型之间有什么区别？

最佳答案

Mu表示递归类型为折叠，而Nu表示它为展开。在Haskell中，这些是同构的，并且是表示同一类型的不同方法。如果您假装Haskell没有任意递归，则这些类型之间的区别会变得更加有趣:Mu f是f的最小(初始)固定点，而Nu f是它的最大(终止)固定点。
f的不动点是T类型，是T和f T之间的同构形式，即一对反函数in :: f T -> T和out :: T -> f T。 Fix类型仅使用Haskell的内置类型递归直接声明同构。但是您可以为Mu和Nu实现in / out。

举个具体的例子，假装你不能写递归值。 Mu Maybe的居民(即:: forall r. (Maybe r -> r) -> r的值)是自然数{0，1，2，...}; Nu Maybe的居民(即:: exists x. (x, x -> Maybe x)的值)是自然变量{0，1，2，...，∞}。考虑一下这些类型的可能值，以了解Nu Maybe为什么会有额外的居民。

如果您想对这些类型有一些直观的认识，那么可以很好地实现以下内容而无需递归(大约按难度递增的顺序):

zeroMu :: Mu Maybe，succMu :: Mu Maybe -> Mu Maybe

zeroNu :: Nu Maybe，succNu :: Nu Maybe -> Nu Maybe，inftyNu :: Nu Maybe

muTofix :: Mu f -> Fix f，fixToNu :: Fix f -> Nu f

inMu :: f (Mu f) -> Mu f，outMu :: Mu f -> f (Mu f)

inNu :: f (Nu f) -> Nu f，outNu :: Nu f -> f (Nu f)

您也可以尝试实现这些，但是它们需要递归:

nuToFix :: Nu f -> Fix f，fixToMu :: Fix f -> Mu f

Mu f是最不固定的点，而Nu f是最大的点，因此编写函数:: Mu f -> Nu f非常容易，但是编写函数:: Nu f -> Mu f却很困难；就像逆流而上。

(在某种意义上，我的意思是写这些类型的更详细的说明，但是对于这种格式来说可能太长了。)

关于haskell - Ed Kmett的递归方案包中的Fix，Mu和Nu有什么区别，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/45580858/