在同一索引处与归纳类型的两个值进行模式匹配

Question

为什么以下不进行类型检查 (coq-8.5pl3)？模式匹配似乎忘记了 u 和 v 具有相同的类型。

Inductive X : Type -> Type :=
| XId : forall a, X a -> X a
| XUnit : X unit.

Fixpoint f {a : Type} (x : X a) (y : X a) : a :=
  match x, y with
  | XId _ u, XId _ v => f u v
  | XUnit, _ => tt
  | _, XUnit => tt
  end.

错误信息：

Error:
In environment
f : forall a : Type, X a -> X a -> a
a : Type
x : X a
y : X a
T : Type
u : X T
y0 : X T
T0 : Type
v : X T0
The term "v" has type "X T0"
while it is expected to have type "X T".

Answer 1

感谢 Anton Trunov 的提示 "convoy pattern"，我设法制作了一个可以编译的版本。

Fixpoint f {a : Type} (x : X a) : X a -> a :=
  match x in X a return X a -> a with
  | XId b u => fun y => match y in X b return X b -> b with
                        | XId c v => fun u => f u v
                        | XUnit => fun _ => tt
                        end u
  | XUnit => fun _ => tt
  end.

在同一索引处与归纳类型的两个值进行模式匹配

Pattern matching with two values of inductive type at the same index

pattern-matching

coq

dependent-type