Coq

Question

这是我尝试在 Coq 中实现的一些简化版本。我有一个归纳类型，比如 foo，它的构造函数采用另一种类型 A，还有一个输入为 A.

的函数

    Inductive foo :=
    | constructor (A : Type) (f : A -> bool).

我还有一个函数，给定一个 foo 类型的对象，告诉我用什么类型构造它。

    Definition foo_type (x : foo) :=
      match x with
      | constructor A f => A
      end.

到目前为止一切顺利。但是现在，我想定义一个函数，它接受一个 foo 类型的对象 x 和一个 foo_type x 类型的对象 y，以及 returns f y，其中 f 是 x.

的构造函数中使用的函数

    Definition foo_func (x : foo) (y : (foo_type x)) :=
      match x with
      | constructor A f => f y
      end.

但是，这不起作用。 Coq 告诉我有一个类型错误：y 是 foo_type x 类型，而它应该是 A.

类型

现在，我知道在这种情况下 foo_type x 的计算结果为 A。使用 this Whosebug question，我找到了一个我可以使用的函数，它将类型 A=B 和元素 a:A 和 returns a 的等式作为输入，但类型B。但是，要使用它，我需要能够在我的函数定义的 match 部分中获得等式 foo_type x = A。这归结为获得等式 x = constructor A f.

所以：在我定义的 match x with 语句中，是否可以提取等式 x = constructor A f？我怎样才能做到这一点？或者有其他方法可以解决这个问题吗？

Answer 1

您需要使用依赖模式匹配（向 Coq 提供一些信息）来获得术语与其 pattern-matched 内容之间的相等性证明：

match x as x0 return x = x0 -> ... with
| pat => fun (e : x = pat) => ...
| ...
end eq_refl

在匹配构造的外部，您可以构建一个在模式匹配期间优化的术语 eq_refl : x = x。这在 Certified programming with dependent types.

中称为护航模式

然而，在你的情况下，有一个相关的、稍微简单的替代方案，仍然使用依赖模式匹配：

Definition foo_func (x : foo) (y : (foo_type x)) :=
    match x as x0 return foo_type x0 -> bool with
    | constructor A f => fun y => f y
    end y.

Coq - 从匹配语句中获取相等性

Coq - Obtaining equality from match statement

types

casting