我如何让 Idris 中的完整性检查器相信我没有使用变量？

Question

我一直无法让 Idris 完整性检查器相信我的函数是完整的。这是我运行遇到的问题的一个简单示例版本。假设我们有一个非常简单的表达式类型，其形式如下：

data SimpleType = Prop | Fn SimpleType SimpleType

data Expr : SimpleType -> Type where
  Var : String -> Expr type
  Lam : String -> Expr rng -> Expr (Fn dom rng)
  App : Expr (Fn dom rng) -> Expr dom -> Expr rng

我想写函数

total sub : {a, b : SimpleType} -> String -> Expr a -> Expr b -> Expr b

SimpleType 需要一个 DecEq 实例，但没什么特别的。问题是如何让类型检查器相信这个函数是完整的。例如，考虑按如下方式实现 sub：

total sub : {a, b : SimpleType} -> String -> Expr a -> Expr b -> Expr b
sub name repl (App l r) = App (substitute name repl l) (substitute name repl r)
sub _ _ expr = expr

（这是不正确的，但这是一个很好的起点。）这会产生错误：

Main.sub is possibly not total due to: repl

乍一看，Idris 似乎无法验证 l 和 r 在结构上小于 (App l r)。也许以下方法会起作用？

total sub : {a, b : SimpleType} -> String -> Expr a -> Expr b -> Expr b
sub name repl expr@(App l r) = App
  (sub name repl (assert_smaller expr l))
  (sub name repl (assert_smaller expr r))
sub _ _ expr = expr

不！

Main.sub is possibly not total due to: repl

事实上，经过进一步的调查，可以发现，当这个程序编译时：

total sub : {a, b : SimpleType} -> String -> Expr a -> Expr b -> Expr b
sub _ _ expr = expr

这个没有！

total sub : {a, b : SimpleType} -> String -> Expr a -> Expr b -> Expr b
sub _ repl expr = expr

现在我不知道如何让 Idris 相信，在最后一个例子中，repl 真的不会干扰整体性。有人知道如何进行这项工作吗？

Answer 1

事实证明这是完整性检查器中的一个错误，它认为您在左侧提到的 'repl' 是库中定义的用于制作简单交互循环的那个。显然不是 - 这只是名称查找中的一个错误 - 解决这个问题很简单。

这已在 git 母版中修复，因此将在下一个版本中修复。同时，使用与 'repl' 不同的名称也可以（我知道这有点烦人，但是你去...）

我如何让 Idris 中的完整性检查器相信我没有使用变量？

How do I convince the totality checker in Idris that I'm not using a variable?

idris