Idris：尝试为 Nat 重新实现 fromInteger 时，完整性检查失败

Question

我有以下代码：

module Test
  data Nat' = S' Nat' | Z'
  Num Nat' where
    x * y = ?hole
    x + y = ?hole
    fromInteger x = if x < 1 then Z' else S' (fromInteger (x - 1))

我收到有关最后一行的错误消息：

Test.idr:6:5:
Prelude.Interfaces.Test.Nat' implementation of Prelude.Interfaces.Num, method fromInteger is
possibly not total due to recursive path Prelude.Interfaces.Test.Nat' implementation of
Prelude.Interfaces.Num, method fromInteger --> Prelude.Interfaces.Test.Nat' implementation of
Prelude.Interfaces.Num, method fromInteger

该函数应该始终给出一个结果，因为最终 fromInteger 的参数将变得足够小以选择第一种情况。但伊德里斯似乎并不明白这一点。这个函数有什么问题，我该如何解决这个错误？

Answer 1

n - 1在结构上不小于n，看这个就观察到Integer不是归纳型。因此，您需要使用像 assert_smaller 这样的技巧来说服完整性检查器您的函数实际上是完整的（参见 Idris tutorial）：

这是它的 current 定义：

 assert_smaller : (x : a) -> (y : b) -> b
 assert_smaller x y = y
It simply evaluates to its second argument, but also asserts to the totality checker that y is structurally smaller than x.

这是 Idris 在其标准库中使用的内容（参见 here）来解决您的问题：

fromIntegerNat : Integer -> Nat
fromIntegerNat 0 = Z
fromIntegerNat n =
  if (n > 0) then
    S (fromIntegerNat (assert_smaller n (n - 1)))
  else
    Z

Idris：尝试为 Nat 重新实现 fromInteger 时，完整性检查失败

Idris: totality check fails when trying to re-implement fromInteger for Nat

recursion

static-analysis

idris

totality