haskell - 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 的不动点是 T 类型，是 T 和 f T 之间的同构，即一对反函数in::f T -> T、out::T -> f T。类型Fix只是使用Haskell的内置类型递归来直接声明同构。但是您可以为 Mu 和 Nu 实现输入/输出。

举一个具体的例子，假设您无法编写递归值。 Mu Maybe 的居民，即值 ::forall r。 (也许 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 -> 修复 f、fixToNu::修复 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 -> 修复 f、fixToMu::修复 f -> Mu f

Mu f 是最小不动点，Nu f 是最大不动点，所以写一个函数 ::Mu f -> Nu f 很容易，但是写一个函数 ::Nu f -> Mu f 就很难了；这就像逆流游泳。

(一度我打算对这些类型写一份更详细的解释，但对于这种格式来说可能有点太长了。)