30

在 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

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

4

1 回答 1

34

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

的不动点是和之间的同构f类型，即一对反函数, 。该类型只是使用 Haskell 的内置类型递归来直接声明同构。但是您可以同时为和实现输入/输出。TTf Tin :: f T -> Tout :: T -> f TFixMuNu

举一个具体的例子，假装你不能写递归值。的居民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很难；这就像逆流而上。

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

于 2017-08-09T04:08:07.687 回答