重写在 Idris 中究竟是如何工作的？

Question

我在 Idris 中写了如下命题：

total
plusOneCommutes : (n : Nat) -> (m : Nat) -> (n + S m = S n + m)
plusOneCommutes Z     k     = Refl
plusOneCommutes (S k) j     = 
 let inductiveHypothesis = plusOneCommutes k j in
   rewrite inductiveHypothesis in Refl

受 Prelude.Nat 源代码的启发，我理解了为什么使用递归调用（在第二种情况下）作为归纳假设来证明这种情况是有意义的。然而，通过漏洞重写的细节，我并没有真正理解发生了什么以及为什么这样做。

如果我写：

plusOneCommutes (S k) j     = ?hole

我从编译器得到以下信息：

- + HolyGrail.hole [P]
 `--               k : Nat
                   j : Nat
     ------------------------------------------------------
      HolyGrail.hole : S (plus k (S j)) = S (S (plus k j))

这似乎不太对。根据 plusOneCommutes 的签名，这个洞的类型应该是 (plus (S k) (S j)) = (plus (S (S k)) j).

更进一步，引入归纳假设，如果我写：

plusOneCommutes (S k) j     = 
 let inductiveHypothesis = plusOneCommutes k j in
   ?hole

然后 hole 的类型变为：

 - + HolyGrail.hole [P]
  `--                    k : Nat
                         j : Nat
       inductiveHypothesis : k + S j = S k + j
      -------------------------------------------------------------------------
       HolyGrail.hole : S (plus k (S j))  = S (S (plus k j))

然后使用 inductiveHypothesis

给出的重写规则

 - + HolyGrail.hole [P]
  `--                    k : Nat
                         j : Nat
       inductiveHypothesis : k + S j = S k + j
             _rewrite_rule : k + S j = S k + j
      -------------------------------------------------------------------------
       HolyGrail.hole : (\replaced => S replaced = S (S (plus k j))) (S k + j)

导致 S (plus (S k) j) = S (S (plus k j)) 这是预期的类型，Idris 可以完成证明，自动将 ?hole 替换为 Refl。

让我感到困惑的是我从签名中推断出的类型与编译器从漏洞中推断出的类型之间出乎意料的差异。如果我主动引入一个错误：

我收到以下消息：

 - + Errors (1)
  `-- HolyGrail.idr line 121 col 16:
      When checking right hand side of plusOneCommutes with expected type
              S k + S j = S (S k) + j

      Type mismatch between
              S (S (plus k j)) = S (S (plus k j)) (Type of Refl)
      and
              S (plus k (S j)) = S (S (plus k j)) (Expected type)

      Specifically:
              Type mismatch between
                      S (plus k j)
              and
                      plus k (S j)

Type mismatch... 部分与上述步骤一致，但 When checking ... 部分给出了我期望的类型。

Answer 1

编译器的以下内容实际上是有道理的：

- + HolyGrail.hole [P]
 `--               k : Nat
                   j : Nat
     ------------------------------------------------------
      HolyGrail.hole : S (plus k (S j)) = S (S (plus k j))

在 = 类型的左侧，您有 n + S m。在 n 上进行模式匹配后，您有 (S k) 并且应该有 S k + S j 类型 plus (S k) (S j)。在中，我解释了一个重点：从 plus 函数的编写方式以及编译器可以在您看到的类型中执行模式匹配这一事实 S (plus k (S j)) 只是应用 [=21] =] 到 (S k) 和 (S j)。与 S n + m.

类似的情况

现在 rewrite。在 Agda 编程语言中 rewrite 只是 Refl 上模式匹配的语法糖。有时你可以用 Idris 中的模式匹配替换 rewrite 但在这种情况下不行。

我们可以尝试做类似的事情。接下来考虑：

total
plusOneCommutes : (n : Nat) -> (m : Nat) -> (n + S m = S n + m)
plusOneCommutes Z     k     = Refl
plusOneCommutes (S k) j     = case plusOneCommutes k j of
    prf => ?hole

编译器接下来说的非常合理：

- + HolyGrail.hole [P]
 `--               k : Nat
                   j : Nat
                 prf : k + S j = S k + j
     ------------------------------------------------------
      HolyGrail.hole : S (plus k (S j)) = S (S (plus k j))

prf 证明 k + S j = S k + j 是有道理的。在使用 rewrite 之后：

plusOneCommutes (S k) j     = case plusOneCommutes k j of
    prf => rewrite prf in ?hole

我们得到了：

- + HolyGrail.hole [P]
 `--               k : Nat
                   j : Nat
                 prf : k + S j = S k + j
       _rewrite_rule : k + S j = S k + j
     -------------------------------------------------------------------------
      HolyGrail.hole : (\replaced => S replaced = S (S (plus k j))) (S k + j)

rewrite 在 Idris 中的行为如下：

接受 Refl : left = right 对象和 expr : t。
在 t 中搜索 left。
将 left 中出现的所有 left 替换为 t 中的 right。

在我们的例子中：

t 是 S (plus k (S j)) = S (S (plus k j))
Refl : plus k (S j) = plus (S k) j
- left 是 plus k (S j)
- right 是 plus (S k) j
Idris 在 t 中将 plus k (S j)（左）替换为 plus (S k) j（右），我们得到 S (plus (S k) j) = S (S (plus k j))。 Idris 可以执行它所做的模式匹配。而S (plus (S k) j)自然就变成了S (S (plus k j)).

重写在 Idris 中究竟是如何工作的？

How exactly does rewrite work in Idris?

dependent-type

idris