Ed Kmett的递归方案包中的Fix、Mu、Nu有什么区别

Question

在 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

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

Answer 1

Mu 将递归类型表示为折叠，Nu 将其表示为展开。在 Haskell 中，它们是同构的，是表示同一类型的不同方式。如果你假装 Haskell 没有任意递归，这些类型之间的区别就变得更有趣了：Mu f 是 f 的最小（初始）不动点，而 Nu f 是它最大的（终端）不动点。

f的不动点是TT和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很难;就像逆水行舟

（有一次我想对这些类型写一个更详细的解释，但对于这种格式来说可能有点太长了。）

Ed Kmett的递归方案包中的Fix、Mu、Nu有什么区别

What is the difference between Fix, Mu and Nu in Ed Kmett's recursion scheme package

haskell

recursive-datastructures

recursion-schemes

fixpoint-combinators