我需要帮助在 Coq 中定义串联

Question

我需要定义一个连接函数，首先是一些上下文，我定义集合 "accepts"

Inductive accepts : Set :=
    | True  : accepts
    .
    .
    .
    | fun_m : accepts -> accepts -> accepts
    | n_fun : nat -> accepts -> accepts
    .

然后我需要能够操作一个非常具体的接受子集：列表中的第一个和最后一个，因此只有 True 和 n_fun。我通过混合感应和记录来做到这一点：

Inductive n_sub : accepts -> Prop :=
  | a1 : n_sub True
  | a2 : forall (n : nat )(A : accepts), n_sub A -> n_sub (n_fun n A).

Record sub : Set := mk_s{ A : accepts ; WS : (s_sub A)}.

如您所见，这将专门为我提供后跟 True 的自然数字符串，因此我想处理产生 n ... k True 的接受子集。考虑到我有两个这样的字符串，我想定义将 "ab... True" 和 "xy...True" 发送到 "ab...xy...True".

的函数

Fixpoint concatenate (A0 A1 : accepts)(x : n_sub A0)(y: n_sub A1):accepts:=
  match x, y with 
    | a1, q => B
    | a2 n A0 x, y => (n_fun n (concatenate A0 A1) )
  end.

显然，这行不通...我已经尝试了 100 种变体：直接使用 accepts 并将内容发送到 void，使用内部记录，将 accepts 和 sub 混合在不同的变体中，等等等等...我只是没有想法，需要有人帮我解决这个连接问题！预先感谢您的帮助！

Answer 1

有时编写可计算谓词比归纳谓词更有帮助（下面是我的 ok，对比你的 n_sub）。

Inductive accepts :=
| valid  : accepts
| fun_m : accepts -> accepts -> accepts
| n_fun : nat -> accepts -> accepts.

Fixpoint ok x :=
  match x with
    | valid => true
    | n_fun _ y => ok y
    | _ => false
  end.

由于 ok 是可计算的，您可以将它用于以后您可能关心的各种事情，但您也可以在证明中使用它（见下文）。

Fixpoint concat x y :=
  match x with
    | valid => y
    | n_fun z zs => n_fun z (concat zs y)
    | _ => y
  end.

concat 对非 ok 输入进行投注。稍后，我将展示一个更严格类型的版本，concatLegit。

Lemma concatOk :
  forall x y,
    ok x = true -> ok y = true -> ok (concat x y) = true.
induction x; auto.
Qed.

Definition legit := { x : accepts & ok x = true }.

Definition concatLegit (x y : legit) : legit.
destruct x as [x p]; destruct y as [y q].
exists (concat x y).
apply concatOk; auto.
Defined.

Print concatLegit.

(*

concatLegit =
fun x y : legit =>
let (x0, p) := x in
let (y0, q) := y in
existT (fun x1 : accepts => ok x1 = true) (concat x0 y0) (concatOk x0 y0 p q)
     : legit -> legit -> legit

*)

Answer 2

这里的问题是，您正在尝试对其类型存在于 Prop 中的事物进行模式匹配，以生成存在于 Set 中的类型 accepts 的事物。 Coq 的类型系统不允许这样做。您要做的是对 accepts 类型的事物进行模式匹配，然后使用属性排除不可能的情况。

这里我将使用交互模式。这允许我只定义我感兴趣的计算部分使用 refine 并留空（使用 _）我稍后将处理的部分。

因为检查 A0 时可能会出现一些不相关的分支，所以我需要概括 return 类型：而不是构建 accepts，我将构建一个证明 n_sub a -> accepts 其中 a 是 A0 匹配的任何内容。

Fixpoint concatenate (A0 A1 : accepts)(x : n_sub A0)(y: n_sub A1):accepts.
refine
  ((match A0 as a return n_sub a -> accepts with
    | True        => fun _      => A1
    | n_fun n A0' => fun Hn_fun => n_fun n (concatenate A0' A1 _ y)
    | _ => _
  end) x).

我现在有两个证明：我需要定义我留空的情况，但这很容易：假设 n_sub (fun_m a a0) 是矛盾的！我可以通过反转来证明 False:

- intro Hf; apply False_rec; inversion Hf.

现在，我必须证明 n_sub A0' 在假设 Hn_fun 且 n_sub (n_fun n A0') 成立的情况下成立。再一次 inversion 就可以了：

- inversion Hn_fun; assumption.

就是这样！这里棘手的部分是确定需要推广的假设并在 dependent pattern-matching 中使用适当的 as ... return ...。通过使用交互模式和 refine 构建不完整证明项的帮助，其余部分变得非常方便。

我需要帮助在 Coq 中定义串联

I need help defining a concatenation in Coq

coq