在 Idris REPL 中使用 cong 进行实验

Question

TL;DR：我想要一个或两个在 Idris REPL 中使用 cong 的例子来帮助我更好地理解它。

通用相等类型在概念上定义如下：

data (=) : a -> b -> Type where
  Refl : x = x

当我第一次遇到这个的时候，我对语法很困惑。（我一直认为 = 是一个运算符而不是一个类型。）但是在 REPL 中使用它帮助我理解了它。例如，我们可以声明类型来表示假等式：

λ> 2 + 2 = 5
4 = 5 : Type
λ> 2 = "wombat"
2 = "wombat" : Type

然而，= 的唯一构造函数是 Refl，只有当两个参数相等时我们才能使用它。

λΠ> the (4 = 4) Refl
Refl : 4 = 4
λΠ> the (4 = 5) Refl
... type mismatch

所以现在我试图通过在 REPL 中进行试验来理解 cong。函数 cong 证明如果两个值相等，则应用它们的功能产生相同的结果。我找到了定义。

  cong : {f : t -> u} -> (a = b) -> f a = f b
  cong Refl = Refl

所以，例如，如果我定义...

λ> :let twoEqTwo = the (2 = 2) Refl
defined

...然后我希望能够证明两边都加 1 会导致另一个相等。

λΠ> :let ty = (S 2 = S 2)
defined
λΠ> the ty (cong twoEqTwo)
    ...type mismatch

谁能告诉我一两个在 REPL 中使用 cong 的例子？

Answer 1

2类型错误。它们默认为 twoEqTwo 中的 Integer 类型，因为它们没有其他约束。看，一个不受约束的 2:

idris> 2
2 : Integer

然而，在 ty 中，你说 S 2。 S 强制整个工作在 Nat:

idris> S 2
3 : Nat

也让 twoEqTwo 在 Nat 中工作：

idris> :let twoEqTwo = the (the Nat 2 = 2) Refl
idris> the (S 2 = S 2) twoEqTwo
Refl : 3 = 3

请注意，如果您让它看到整个表达式，类型推断可以自行解决这个问题：

idris> the (S 2 = S 2) (cong (the (2 = 2) Refl))
Refl : 3 = 3

Experimenting with cong in the Idris REPL