为什么 Idris 的 Refl 有时不进行类型检查？

Question

我正在研究 Idris 的书，并且正在做第一个证明练习。

通过练习来证明 same_lists，我能够像这样实现它，因为匹配 Refl 强制 x 和 y 统一：

total same_lists : {xs : List a} -> {ys : List a} ->
    x = y -> xs = ys -> x :: xs = y :: ys
same_lists Refl Refl = Refl

然而，当我试图以同样的方式证明其他东西时，我得到了不匹配。例如：

total allSame2 : (x, y : Nat) -> x = y -> S x = S y
allSame2 x y Refl = Refl

编译器说：

Type mismatch between
   y = y (Type of Refl)
and
   x = y (Expected type)

如果我在 = 之后进行大小写匹配，无论是显式还是使用 lambda，它都会按预期工作：

total allSame2 : (x : Nat) -> (y : Nat) -> x = y -> S x = S y
allSame2 x y = \Refl => Refl

这里有什么区别？

另一个有效的修改是使有问题的参数隐式化：

total allSame2 : {x : Nat} -> {y : Nat} -> x = y -> S x = S y
allSame2 Refl = Refl

Answer 1

我不知道所有的细节，但我可以给你一个大概的概念。在 Idris 中，命名函数的参数列表是特殊的，因为它是依赖模式匹配的一部分。当您进行模式匹配时，它还会重写其他参数。

same_lists x y Refl = Refl 无效，我粗略猜测，因为 Idris 将 x 和 y 重写为相同的，然后不允许您为此赋予不同的名称单值——我希望有人能对这种机制给出更好的解释。相反，您可以使用 same_lists x x Refl = Refl — 请注意名称 x 并不重要，只是两个站点使用相同的名称。

lambda 参数与命名参数列表不同。因此，由于您在 lambda 中进行匹配，Idris 只会在此时重写其他参数。关键是，对于第一个示例，Idris 想要一次完成所有操作，因为它是同一参数列表的一部分。

对于最后一个示例，唯一的变化是您没有为参数指定不同的名称。使用 all_same _ _ Refl = Refl 也是有效的。当参数是隐式时，Idris 会为您正确填写。

最后你可以考虑 same_lists = \x, y, Refl => Refl 这也有效。这是因为 Idris 不会重写未命名的参数列表（即 lambda 参数）。

为什么 Idris 的 Refl 有时不进行类型检查？

Why does Idris' Refl sometimes not type-check?

idris