Idris - 基于可判定 属性 的类型计算不进行类型检查

Question

我在 Idris 中遇到问题，我想根据可判定的 属性 创建类型级 "check"，如果 属性 成立，我会得到我想要的类型，但如果 属性 失败，我会得到 Unit (())，表示程序处于不一致状态（如果我决定将其用作我的程序，则不应编译原始类型）。

这是一个例子：

TestType : {k : Nat} -> Nat -> Vect k Nat -> Type
TestType n ls with (isElem n ls)
  TestType n ls | Yes _ = Nat
  TestType n ls | No _ = ()

mkTestTypeFromNat : (n : Nat) -> (ls : Vect k Nat) -> Elem n ls -> Nat -> TestType {k=k} n ls
mkTestTypeFromNat n ls prf res = res

mkTestTypeFromUnit : (n : Nat) -> (ls : Vect k Nat) -> Not (Elem n ls) -> TestType {k=k} n ls
mkTestTypeFromUnit n ls prf = ()

当我尝试编译它时，它显示以下错误：

When checking right hand side of mkTestTypeFromNat:
Type mismatch between
           Nat (Type of n)
   and
           with block in Extensible_Records.TestType n
                                                     k
                                                     ls
                                                     (isElem n ls) (Expected type)

When checking right hand side of mkTestTypeFromUnit:
Type mismatch between
           () (Type of ())
   and
           with block in Extensible_Records.TestType n
                                                     k
                                                     ls
                                                     (isElem n ls) (Expected type)

在这些 mkTestTypeFrom_ 函数的每一个中，我都提供了 deciable 属性 的证明，或者证明元素在列表中，或者证明它不在列表中。类型检查器不应该意识到它有这些证明，并且能够毫无问题地计算 with (isElem n ls) 部分，在每种情况下都给我正确的类型吗？还是我遗漏了一些东西来说服类型检查器？

Answer 1

在你使用它之前，仅仅拥有证据并不能真正帮助你。这是我能为你的类型想出的最好的；我不知道代码是否会被合理地优化，或者如果没有，是否有办法使它们高效。编译器肯定会认识到每个案例分析只有一个可到达的分支。我不太清楚的是，它是否会意识到因此不需要评估受检者。

mkTestTypeFromNat : (n : Nat) -> (ls : Vect k Nat) -> Elem n ls -> Nat -> TestType {k=k} n ls
mkTestTypeFromNat n ls prf res with (isElem n ls)
  mkTestTypeFromNat n ls prf res | (Yes x) = res
  mkTestTypeFromNat n ls prf res | (No contra) = absurd (contra prf)

mkTestTypeFromUnit : (n : Nat) -> (ls : Vect k Nat) -> Not (Elem n ls) -> TestType {k=k} n ls
mkTestTypeFromUnit n ls prf with (isElem n ls)
  mkTestTypeFromUnit n ls prf | (Yes x) = absurd (prf x)
  mkTestTypeFromUnit n ls prf | (No contra) = ()