模式匹配情况下的统一
Unification in pattern matching case
我试图编写一个类型为 forall n, option (n = 1)
的函数。
我选择option
作为reflect
的替代方案,避免给出否定案例的证明。所以 Some
扮演角色 ReflectT
并持有证明,而 None
不持有反证明。
Definition is_1 n: bool:=
match n with
1 => true |
_ => false
end.
Lemma is_1_complete : forall n, is_1 n = true -> n = 1.
intros.
destruct n. simpl in H. discriminate.
destruct n. reflexivity.
simpl in H. discriminate.
Qed.
Lemma a_nat_is_1_or_not: forall n, option (n = 1).
intros.
cut (is_1 n = true -> n = 1).
-
intros.
destruct n. exact None.
destruct n. simpl in H. exact (Some (H (eq_refl))).
exact None.
-
exact (is_1_complete n).
Qed.
我已经完成了战术。 a_nat_is_1_or_not
就是证明。而且我认为我可以直接写定义,所以我尝试了。
Definition a_nat_is_1_or_not' n: option (n = 1) :=
match is_1 n with
true => Some (is_1_complete n eq_refl)
| false => None
end.
但是 Coq 说
Error:
In environment
n : nat
The term "eq_refl" has type "is_1 n = is_1 n"
while it is expected to have type "is_1 n = true" (cannot unify "is_1 n" and
"true").
在自身模式匹配的true
情况下,is_1 n
似乎不能统一到true
所以我尝试了一个更简单的例子。
Definition every_true_is_I x: x = I :=
match x with
I => eq_refl
end.
有效。
a_nat_is_1_or_not'
和 every_truer_is_I
有什么区别?
我错过了什么吗?我可以做什么来编写 forall n, is_1 n = true -> n = 1.
的有效定义?
不同之处在于,在 a_nat_is_1_or_not'
中,您依赖于类型为 is_1 n = true -> _
的外部术语。如果你想让 a_nat_is_1_or_not'
看起来像 every_true_is_I
,你必须确保 is_1 n
的所有出现都被模式匹配覆盖:
Definition a_nat_is_1_or_not' n: option (n = 1) :=
match is_1 n as b return ((b = true -> _) -> _) with
| true => fun H => Some (H eq_refl)
| false => fun _ => None
end (is_1_complete n).
注意 is_1_complete
是如何在模式匹配之外实例化的,以便处理它出现的 is_1 n
(重命名为 b
)。
还有另一种方法,也许更符合习惯。与其概括整个上下文,不如保留足够的信息来填补所有漏洞:
Definition a_nat_is_1_or_not' n: option (n = 1) :=
match is_1 n as b return (is_1 n = b -> _) with
| true => fun H => Some (is_1_complete n H)
| false => fun _ => None
end eq_refl.
但思路是一样的。通过在模式匹配之外实例化 eq_refl
,在 is_1 n
.
上进行匹配时不会丢失任何信息
我试图编写一个类型为 forall n, option (n = 1)
的函数。
我选择option
作为reflect
的替代方案,避免给出否定案例的证明。所以 Some
扮演角色 ReflectT
并持有证明,而 None
不持有反证明。
Definition is_1 n: bool:=
match n with
1 => true |
_ => false
end.
Lemma is_1_complete : forall n, is_1 n = true -> n = 1.
intros.
destruct n. simpl in H. discriminate.
destruct n. reflexivity.
simpl in H. discriminate.
Qed.
Lemma a_nat_is_1_or_not: forall n, option (n = 1).
intros.
cut (is_1 n = true -> n = 1).
-
intros.
destruct n. exact None.
destruct n. simpl in H. exact (Some (H (eq_refl))).
exact None.
-
exact (is_1_complete n).
Qed.
我已经完成了战术。 a_nat_is_1_or_not
就是证明。而且我认为我可以直接写定义,所以我尝试了。
Definition a_nat_is_1_or_not' n: option (n = 1) :=
match is_1 n with
true => Some (is_1_complete n eq_refl)
| false => None
end.
但是 Coq 说
Error:
In environment
n : nat
The term "eq_refl" has type "is_1 n = is_1 n"
while it is expected to have type "is_1 n = true" (cannot unify "is_1 n" and
"true").
在自身模式匹配的true
情况下,is_1 n
似乎不能统一到true
所以我尝试了一个更简单的例子。
Definition every_true_is_I x: x = I :=
match x with
I => eq_refl
end.
有效。
a_nat_is_1_or_not'
和 every_truer_is_I
有什么区别?
我错过了什么吗?我可以做什么来编写 forall n, is_1 n = true -> n = 1.
的有效定义?
不同之处在于,在 a_nat_is_1_or_not'
中,您依赖于类型为 is_1 n = true -> _
的外部术语。如果你想让 a_nat_is_1_or_not'
看起来像 every_true_is_I
,你必须确保 is_1 n
的所有出现都被模式匹配覆盖:
Definition a_nat_is_1_or_not' n: option (n = 1) :=
match is_1 n as b return ((b = true -> _) -> _) with
| true => fun H => Some (H eq_refl)
| false => fun _ => None
end (is_1_complete n).
注意 is_1_complete
是如何在模式匹配之外实例化的,以便处理它出现的 is_1 n
(重命名为 b
)。
还有另一种方法,也许更符合习惯。与其概括整个上下文,不如保留足够的信息来填补所有漏洞:
Definition a_nat_is_1_or_not' n: option (n = 1) :=
match is_1 n as b return (is_1 n = b -> _) with
| true => fun H => Some (is_1_complete n H)
| false => fun _ => None
end eq_refl.
但思路是一样的。通过在模式匹配之外实例化 eq_refl
,在 is_1 n
.