Idris 将证明传递给参数为 LTE 的函数

Question

我有一个函数可以减去两个 Nat。我如何证明我传递给它的第一个参数实际上小于第二个

dummy : (k : Nat) -> (n : Nat) -> {auto smaller : LTE k n} -> Nat
dummy k n = n - k

我已经尝试了几个不起作用的解决方案

smallerThan : (k : Nat) -> (n : Nat) -> Maybe (LTE k n)
smallerThan Z k = Just (LTEZero {right=k})
smallerThan (S k) Z = Nothing
smallerThan (S k) (S n) = case isLTE k n of
                            Yes prf => Just prf
                            No contra => Nothing

smallerThan (S k) (S n) = case smallerThan k n of
                            Nothing => Nothing
                            Just lte => Just (cong lte)

我知道我的洞 smallerThan (S k) (S n) = Just (?hole) 的类型是 LTE (S k) (S n) 但如何正确使用 fromLteSucc 或任何其他功能来实现它？

我找到了 this question，但没有我需要的证据就解决了。

您能否提示我做错了什么以及如何正确实施这种检查？

Answer 1

在您第二次尝试 Just 的情况下，由于递归，您得到了 LTE k n 的证明，但正如您所说，需要 LTE (S k) (S n)。您可以通过两种方式找到缺失的步骤。 Search 在该类型函数的 REPL 中：

Idris> :search LTE k n -> LTE (S k) (S n)
= Prelude.Nat.LTESucc : LTE left right -> LTE (S left) (S right)
If n <= m, then n + 1 <= m + 1

或更简单，通过 REPL 或编辑器使用 proof search（我可以只使用 <space>p 来解决 ?hole，这是 Idris IMO 中最好的功能！）。这也会导致

 smallerThan (S k) (S n) = case smallerThan k n of
                             Nothing => Nothing
                             Just lte => Just (LTESucc lte)

此外，isLTE 是 smallerThan 只是 Dec 比 Maybe 更强大，因为在否定的情况下你得到了 k 的证明不小于或等于 n。所以 isLTE 没有错误，而 smallerThan 总是 return Nothing.

您可以在 dummy 调用函数中使用它，例如：

foo : Nat -> Nat -> Nat
foo x y = case isLTE x y of
   Yes prf => dummy x y
   No contra => Z

Idris 将证明传递给参数为 LTE 的函数

Idris pass proof to a function that arguments are LTE

ghc

idris

dependent-type

theorem-proving