Idris 中的非零整数类型？

Question

我有一个函数 return 是一个应该为非零的整数，我想通过它的 return 类型来保证这一点。你如何在 Idris 中表达非零整数的类型？

Answer 1

根据您的功能，有不同的方法。如果你使用 Nat 作为 return 类型，你可以阅读 Theorem Proving in the Idris Tutorial。一个例子是 inc 增加了一个 Nat 和一个证明 incNotZ，对于每个 n : Nat，Not (inc n = Z):

inc : Nat -> Nat
inc n = S n

incNotZ : (n : Nat) -> Not (Z = inc n)
incNotZ n p = replace {P = incNotZTy} p ()
  where
    incNotZTy : Nat -> Type
    incNotZTy Z = ()
    incNotZTy (S k) = Void

有时您可以在结果旁边生成证明，f.e.:

data NotZero : Nat -> Type where
  MkNotZero : (n : Nat) -> NotZero (S n)

inc : (n : Nat) -> NotZero (S n)
inc n = MkNotZero n

rev : NotZero n -> Not (n = 0)
rev (MkNotZero n) = SIsNotZ -- from Prelude.Nat

这里NotZero n证明n不为零，因为n只能通过(S n)构造。事实上，可以使用 rev.

将任何 NotZero n 转换为 Not (n = 0)

如果您的证明类型适合函数，这通常是更好的选择。由于 inc 和 NotZero 都具有 (n : Nat) -> … (S n)，您可以免费获得证明。另一方面，如果你想证明一个函数的某些东西，属性它持有什么，比如 plus 的交换性或对称性，需要第一种方法。

如果您将 Int 用作 return 类型，这通常没有用，因为 Int 可能会溢出并且 Idris 不能争论 Int (或 Integer 或 Float 或 …):

*main> 10000000000000000000 * (the Int 5)
-5340232221128654848 : Int

所以通常的方法是在运行时构造一个证明以查看非零性是否成立：

inc' : Int -> Int
inc' i = abs i + 1

incNotZ' : (i : Int) -> Either (So (inc' i == 0)) (So (not (inc' i == 0)))
incNotZ' i = choose (inc' i == 0)

然后当您调用 incNotZ' 时，您可以匹配结果以在右侧获得证明或在左侧处理错误情况。

如果您正在使用例如非溢出 Integer 并且真的非常确定您的函数永远不会 return 0，您可以强制编译器相信您：

inc' : Integer -> Integer
inc' i = abs i + 1

incNotZ' : (i : Integer) -> Not (0 = inc' i)
incNotZ' i = believe_me

Idris 中的非零整数类型？

Type of nonzero integers in Idris?

types

idris