将输入参数限制为函数

Question

假设我想将斐波那契函数定义为以下函数：

fibo : Int -> Int
fibo 1 = 1
fibo 2 = 2
fibo n = fibo (n-1) + fibo (n-2)

这个函数显然不是总函数，因为它对小于 1 的整数没有定义，所以我需要以某种方式限制输入参数..

我试过定义一个新的数据类型 MyInt。沿线的东西：

-- bottom is the lower limit
data MyInt : (bottom: Int) -> (n: Int) -> Type
  where
    ...

fibo : MyInt 1 n -> Int
...

不过我很快就迷路了。

如何将输入参数限制为例如我的 fibo 函数为 1 或更大的整数值？

Answer 1

实际上有两个原因导致 Idris 无法将 fibo 函数识别为合计。首先，正如您所指出的，它不是为小于 1 的整数定义的，但其次，它递归地调用自身。尽管 Idris 能够识别递归函数的整体性，但通常只有在可以证明递归调用的参数比原始参数 (例如，如果一个函数接收一个列表作为参数，它可以用列表的尾部调用自己而不必牺牲整体性，因为尾部是原始列表的子结构，因此更接近 Nil)。 (n-1) 和 (n-2) 等表达式的问题是，当它们属于 Int 类型时，尽管它们 在数值上 小于 n，但它们是不是 结构上 更小，因为 Int 不是归纳定义的，因此没有基本情况。因此完整性检查器无法满足自己递归最终总是会达到基本情况（即使这对我们来说似乎很明显），因此它不会认为 fibo 是完整的。

首先，让我们解决递归问题。我们可以使用归纳定义的数据类型来代替 Int，例如 Nat:

data Nat =
  Z | S Nat

（一个自然数要么是零，要么是另一个自然数的后继数。）

这允许我们将 fibo 重写为：

fibo : Nat -> Int
fibo (S Z)     = 1
fibo (S (S Z)) = 2
fibo (S (S n)) = fibo (S n) + fibo n

（请注意在递归情况下，我们不是显式地计算 (n-1) 和 (n-2)，而是通过对参数进行模式匹配来生成它们，从而向 Idris 证明它们在结构上更小。）

这个 fibo 的新定义仍然不完全，因为它缺少 Z 的案例（即零）。如果我们不想提供这种情况，那么我们需要向 Idris 保证不会允许这种情况发生。我们可以做到这一点的一种方法是要求证明 fibo 的参数大于或等于 1（或者等效地，1 小于或等于参数）：

fibo : (n : Nat) -> LTE 1 n -> Int
fibo Z LTEZero impossible
fibo Z (LTESucc _) impossible
fibo (S Z) _ = 1
fibo (S (S Z)) _ = 2
fibo (S (S (S n))) _ = fibo (S (S n)) (LTESucc LTEZero) + fibo (S n) (LTESucc LTEZero)

LTE 1 n 是其值证明 1 ≤ n（在自然数范围内）的类型。 LTEZero表示零≤任意自然数的公理，LTESucc表示如果n≤m，则（n的后继) ≤（m 的继承者）。 impossible 关键字表示给定的情况不可能发生。在上面的定义中，fibo的第一个参数不可能为零，因为没有办法证明1≤0。对于任何其他自然数n，我们可以证明1≤n 使用 (LTESucc LTEZero).

现在终于 fibo 是总和了，但是必须为它提供其参数大于或等于 1 的显式证明是相当麻烦的。幸运的是，我们可以将证明参数标记为 auto隐式：

fibo : (n : Nat) -> {auto p : LTE 1 n} -> Int
fibo Z {p = LTEZero} impossible
fibo Z {p = (LTESucc _)} impossible
fibo (S Z) = 1
fibo (S (S Z)) = 2
fibo (S (S (S n))) = fibo (S (S n)) + fibo (S n)

Idris 现在会在可能的情况下自动找到 1 ≤ n 的证明，否则我们仍然需要自己提供。

_{* 可能有一些与 codata 相关的微妙之处，我在这里没有意识到，但这是广泛的原则。}

将输入参数限制为函数

Constraining input arguments to a function

idris