在 Coq 模式匹配中使用上下文信息

Question

我想定义一个函数app_1，将一个n元函数f : X ^^ n --> Y转换成一个新函数f' : (Z -> X) ^^ n --> Y，前提是有一个[=17] =] 对其所有参数应用一次。例如，

Example ex1 : app_1 plus 2 S pred = 4.
trivial. Qed.

app_1 plus 2 能够将一元函数 S 和 pred 作为参数，因为它首先将它们都应用于 2，然后将结果应用于plus.

这是我对 app_1 的尝试定义：

Fixpoint app_1 {X Y Z : Type} {n : nat} 
(f : X ^^ n --> Y) (z : Z) :
(Z -> X) ^^ n --> Y :=
match n return ((Z -> X) ^^ n --> Y) with
| O    => f
| S n' => fun g => app_1 (f (g z)) z
end.

这是行不通的，因为 Coq 不喜欢子句 | O => f，并说：

The term "f" has type "X ^^ n --> Y" while it is expected to have type "(Z -> X) ^^ 0 --> Y".

但是如果n = O，X ^^ n --> Y = X ^^ 0 --> Y = Y = (Z -> X) ^^ 0 --> Y，那么就不是类型不匹配。问题是 Coq 不能使用上下文信息 n = O 来计算等价性。

一些初步搜索表明这是一个众所周知的问题，但是如何将这些讨论应用到这个案例中有点令人困惑。例如，an almost identical question on SO 是使用 return 解决的，这也是我（有点）在上面尝试过的，但无济于事。

有没有办法使这种模式匹配起作用？

Answer 1

您可以推迟到 n 完善之后再获取您的论点：

Fixpoint app_1 {X Y Z : Type} {n : nat}
  : (X ^^ n --> Y) -> Z -> (Z -> X) ^^ n --> Y :=
  match n return (X ^^ n --> Y) -> Z -> (Z -> X) ^^ n --> Y with
    | O    => fun f _ => f
    | S n' => fun f z g => app_1 (f (g z)) z
  end.

到f绑定的时候，它的类型已经变成了X ^^ 0 --> Y，这样就可以了。

编辑：啊，我正要添加这个，但亚瑟抢先一步！

Fixpoint app_1 {X Y Z : Type} {n : nat} (f: X ^^ n --> Y) (z: Z)
  : (Z -> X) ^^ n --> Y :=
  match n return X ^^ n --> Y -> ((Z -> X) ^^ n --> Y) with
    | O    => fun f => f
    | S n' => fun f' g => app_1 (f' (g z)) z
  end f.

Answer 2

像往常一样，您必须应用 convoy 模式（参见 Adam Chlipala 的 CPDT 书）并使模式匹配 return 成为函数:

Require Import Coq.Numbers.NaryFunctions.

Fixpoint app_1 {X Y Z : Type} {n : nat}
(f : X ^^ n --> Y) (z : Z) :
(Z -> X) ^^ n --> Y :=
match n return (X ^^ n --> Y) -> ((Z -> X) ^^ n --> Y) with
| O    => fun f => f
| S n' => fun f g => app_1 (f (g z)) z
end f.

为了使用关于f类型的信息，需要重新抽象：在每个分支中，它都会有正确的类型。

在 Coq 模式匹配中使用上下文信息

Using contextual information in Coq pattern matching

pattern-matching

coq