Idris 不会在指数定律的证明中扩展“mult”

Question

我正在尝试在 Idris 中写一个 2^n * 2^m = 2^(n+m) 的证明。现在我有这个：

expLaw : (power 2 n) * (power 2 m) = power 2 (n + m)
expLaw {n=Z} {m} = plusZeroRightNeutral (power 2 m)
expLaw {n=S n'} {m=m'} = 
  trans (multAssociative 2 (power 2 n') (power 2 m')) $ 
  cong {f=mult 2} $ expLaw {n=n'} {m=m'}

这给了我错误：

When checking an application of function trans:
        Type mismatch between
                mult 2 (power 2 n' * power 2 m') = mult 2 (power 2 (n' + m')) (Type of cong powExp)
        and
                mult (mult 2 (power 2 n')) (power 2 m') = plus (power 2 (plus n' m')) (plus (power 2 (plus n' m')) 0) (Expected type)

        Specifically:
                Type mismatch between
                        mult 2 (power 2 (n' + m'))
                and
                        plus (power 2 (plus n' m')) (plus (power 2 (plus n' m')) 0)

据我所知，这实际上是在说它看到 2 * 2^(n+m) 而它想要 2^(n+m) + (2^(n+m) + 0)。然而，根据 mult 的定义，前者应该简单地简化为后者。特别是，以下编译没有问题：

foo : 2 * a = a + (a + 0)
foo = Refl

对我来说，这表明扩展正在按我的预期进行。但出于某种原因，在我的 expLaw 实现中，编译器卡住了。我想知道它是否与 mult 和 plus 与 * 和 + 的使用有关，但我不确定。我该如何解决这个问题？

或者，如果有人有更好的实现方法expLaw，我会很高兴听到。

Answer 1

它有助于使用 let … in … 块逐步添加证明，因此您可以轻松地检查类型。错误发生在trans下，所以给定

expLaw : (power 2 n) * (power 2 m) = power 2 (n + m)
expLaw {n=Z} {m} = plusZeroRightNeutral (power 2 m)
expLaw {n=S n'} {m=m'} =
  let prf1 = cong {f=mult 2} $ expLaw {n=n'} {m=m'} in
  let prf2 = multAssociative 2 (power 2 n') (power 2 m') in
  ?hole

> :t hole
  m' : Nat
  n' : Nat
  prf1 : plus (mult (power 2 n') (power 2 m'))
              (plus (mult (power 2 n') (power 2 m')) 0) =
         plus (power 2 (plus n' m')) (plus (power 2 (plus n' m')) 0)
  prf2 : plus (mult (power 2 n') (power 2 m'))
              (plus (mult (power 2 n') (power 2 m')) 0) =
         mult (plus (power 2 n') (plus (power 2 n') 0)) (power 2 m')
--------------------------------------
hole : mult (plus (power 2 n') (plus (power 2 n') 0)) (power 2 m') =
       plus (power 2 (plus n' m')) (plus (power 2 (plus n' m')) 0)

您可以看到等式 prf2 : a = b、prf1 : a = c 的顺序与 trans : (a = b) -> (b = c) -> a = c 不匹配。但是用一个简单的 sym : (a = b) -> b = a 就可以了。所以你几乎拥有它。 :-)

 …
 let prf3 = trans (sym prf2) prf1 in
 prf3

Idris 不会在指数定律的证明中扩展“mult”

Idris won't expand `mult` in proof of exponent law

theorem-proving

idris