为什么归纳数据类型禁止像`data Bad a=C（Bad a->a）`这样的类型递归发生在->前面？

Question

Agda手册 归纳数据类型和模式匹配 国家:

为了确保正常化，归纳事件必须出现在严格的正位置。例如，不允许使用以下数据类型:

data Bad : Set where
  bad : (Bad → Bad) → Bad

因为在构造函数的参数中有一个坏的否定出现。

为什么这种要求对于归纳数据类型是必要的？

Answer 1

你给出的数据类型是特殊的，因为它是 无类型 lambda微积分。

data Bad : Set where
  bad : (Bad → Bad) → Bad

unbad : Bad → (Bad → Bad)
unbad (bad f) = f

让我们看看如何。回想一下，无类型的lambda演算有这些术语:

 e := x | \x. e | e e'

我们可以定义一个翻译 [[e]] 从无类型的lambda演算项到类型的Agda项 Bad （虽然不是在Agda）:

[[x]]     = x
[[\x. e]] = bad (\x -> [[e]])
[[e e']]  = unbad [[e]] [[e']]

现在，您可以使用自己喜欢的非终止无类型lambda项来生成类型的非终止项 Bad.例如，我们可以翻译 (\x. x x) (\x. x x) 到类型的非终止表达式 Bad 下面:

unbad (bad (\x -> unbad x x)) (bad (\x -> unbad x x))

虽然类型恰好是这个参数的一个特别方便的形式，但它可以通过一些工作推广到任何递归负出现的数据类型。

Answer 2

在Turner，D.A.中给出了这样的数据类型如何允许我们居住任何类型的例子。(2004-07-28), 总函数编程,教派。3.1，第758页 第2条:类型递归必须是协变的."

---

让我们用Haskell做一个更详细的例子。我们将从"坏"递归数据类型开始

data Bad a = C (Bad a -> a)

及建造 Y组合器 从它没有任何其他形式的递归。这意味着拥有这样的数据类型允许我们构造任何类型的递归，或者通过无限递归来构造任何类型。

无类型lambda演算中的Y组合器定义为

Y = λf.(λx.f (x x)) (λx.f (x x))

它的关键是我们申请 x 对自己 x x.在类型化语言中，这是不可能的，因为没有有效的类型 x 可能有。但我们的 Bad 数据类型允许此模添加/删除构造函数:

selfApp :: Bad a -> a
selfApp (x@(C x')) = x' x

服用；服用 x :: Bad a, ，我们可以解开它的构造函数，并将里面的函数应用到 x 本身。一旦我们知道如何做到这一点，就很容易构造Y组合器:

yc :: (a -> a) -> a
yc f =  let fxx = C (\x -> f (selfApp x))  -- this is the λx.f (x x) part of Y
        in selfApp fxx

请注意 都不是 selfApp 也没有 yc 是递归的，没有递归调用函数本身。 递归只出现在我们的递归数据类型中。

我们可以检查构造的combinator确实做了它应该做的事情。我们可以做一个无限循环:

loop :: a
loop = yc id

或者，让我们说 GCD:

gcd' :: Int -> Int -> Int
gcd' = yc gcd0
  where
    gcd0  :: (Int -> Int -> Int) -> (Int -> Int -> Int)
    gcd0 rec a b  | c == 0     = b
                  | otherwise  = rec b c
      where c = a `mod` b