在 Coq 中，如何构造 'sig' 类型的元素

Question

用类型的简单归纳定义A:

Inductive A: Set := mkA : nat-> A.

(*get ID of A*)
Function getId (a: A) : nat := match a with mkA n => n end.

还有一个子类型定义：

(* filter that test ID of *A* is 0 *)
Function filter (a: A) : bool := if (beq_nat (getId a) 0) then true else false.

(* cast bool to Prop *)
Definition IstrueB (b : bool) : Prop := if b then True else False.

(* subtype of *A* that only interests those who pass the filter *)
Definition subsetA : Set := {a : A | IstrueB (filter a) }.

我尝试使用此代码在 filter 通过时将 A 的元素转换为 subsetA，但未能方便 Coq 认为它是 [=33 的元素的有效构造=]类型：

Definition cast (a: A) : option subsetA :=
match (filter a) with
 | true => Some (exist _ a (IstrueB (filter a)))
 | false => None
end.

错误：

In environment
a : A
The term "IstrueB (filter a)" has type "Prop"
while it is expected to have type "?P a"
(unable to find a well-typed instantiation for "?P": cannot ensure that
"A -> Type" is a subtype of "?X114@{__:=a} -> Prop").

因此，Coq 需要 (IstrueB (filter a)) 类型的实际证明，但我提供的是 Prop.

类型

您能否阐明如何提供此类类型？谢谢你。

Answer 1

首先，有标准的 is_true 包装器。您可以像这样明确地使用它：

Definition subsetA : Set := {a : A | is_true (filter a) }.

或隐式使用强制机制：

Coercion is_true : bool >-> Sortclass.
Definition subsetA : Set := { a : A | filter a }.

接下来，filter a 上的非依赖模式匹配不会将 filter a = true 传播到 true 分支。您至少有三个选择：

使用策略构建您的 cast 功能：

Definition cast (a: A) : option subsetA.
  destruct (filter a) eqn:prf.
  - exact (Some (exist _ a prf)).
  - exact None.
Defined.

显式使用依赖模式匹配（在 Whosebug 或 CDPT 中搜索 "convoy pattern"）：

Definition cast' (a: A) : option subsetA :=
  match (filter a) as fa return (filter a = fa -> option subsetA) with
  | true => fun prf => Some (exist _ a prf)
  | false => fun _ => None
  end eq_refl.

使用Program设施：

Require Import Coq.Program.Program.

Program Definition cast'' (a: A) : option subsetA :=
  match filter a with
  | true => Some (exist _ a _)
  | false => None
  end.

在 Coq 中，如何构造 'sig' 类型的元素

In Coq, How to construct an element of 'sig' type

types

casting

subtype

coq