让我们从电子邮件的Agda模式中获得一些帮助:
recâzfsuccnâ¡fnrecâzfn : {C : Set} {z : C} {f : â â C â C} (n : â) â
recâ z f (succ n) â¡ f n (recâ z f n)
recâzfsuccnâ¡fnrecâzfn {f = f} n = {!!}
如果我们通过键入
C-u C-u C-c C-,
(每次我觉得我想在《凡人康巴特》中引用死亡),我们会看到(我稍微清理了一下你的定义)
Goal: f
(projâ
(iter (0 , .z) (λ nx â succ (projâ nx) , f (projâ nx) (projâ nx))
n))
(projâ
(iter (0 , .z) (λ nx â succ (projâ nx) , f (projâ nx) (projâ nx))
n))
â¡
f n
(projâ
(iter (0 , .z) (λ nx â succ (projâ nx) , f (projâ nx) (projâ nx))
n))
第二个参数
f
两边相等,所以我们可以写
recâzfsuccnâ¡fnrecâzfn {f = f} n = cong (λ m -> f m (recâ _ f n)) {!!}
哪里
cong : â {a b} {A : Set a} {B : Set b}
(f : A â B) {x y} â x â¡ y â f x â¡ f y
cong f refl = refl
现在的目标是
Goal: projâ (iter (zero , .z) (succâ f) n) â¡ n
这是一个简单的引理
lem : {C : Set} {z : C} {f : â â C â C} (n : â)
â projâ (iter (zero , z) (succâ f) n) â¡ n
lem = indâ refl (λ _ -> cong succ)
所以
recâzfsuccnâ¡fnrecâzfn : {C : Set} {z : C} {f : â â C â C} (n : â) â
recâ z f (succ n) â¡ f n (recâ z f n)
recâzfsuccnâ¡fnrecâzfn {f = f} n = cong (λ m -> f m (recâ _ f n)) (lem n)
The whole code
.