在 Coq 中修改、使用和应用 let 表达式

Question

我不确定如何在 coq 中应用 let 表达式。这来自 PF 中的 selection 排序示例。

一旦select函数被定义，这个引理就被证明了。

Lemma select_perm: forall x l,
  let (y,r) := select x l in
   Permutation (x::l) (y::r).

这些是一些用例以了解其工作原理。

Compute select_perm  3 [10;32;4;6;5].
     = select_perm 3 [10; 32; 4; 6; 5]
     : let (y, r) := select 3 [10; 32; 4; 6; 5] in
       Permutation [3; 10; 32; 4; 6; 5] (y :: r)

Compute select 3 [10; 32; 4; 6; 5].
  = (3, [10; 32; 4; 6; 5])
       : nat * list nat

我如何进一步评估它以揭示实际的排列 - 类似于 Compute ((select_perm 3 [10;32;4;6;5]) (select 3 [10; 32; 4; 6; 5]))?

我不确定如何在应用下面的定理时使用这个引理。

Lemma selsort_perm:
  forall n,
  forall l, length l = n -> Permutation l (selsort l n).
Proof.
  intros.
  generalize dependent n.
  induction l; intros.
  - subst.
    simpl.
    constructor.
  - subst. simpl.
    destruct (select a l) eqn:?.

有了相应的目标，我想以某种方式应用select_perm(apply (select_perm a l))。

  a : nat
  l : list nat
  IHl : forall n : nat, length l = n -> Permutation l (selsort l n)
  n : nat
  l0 : list nat
  Heqp : select a l = (n, l0)
  ============================
  Permutation (a :: l) (n :: selsort l0 (length l))

或者，相应地，通过传递性证明 assert (Permutation (a :: l) (n :: l0)) 并以某种方式将以下 Heqp 带入具有新目标的 let 表达式中。有没有一种简单的方法可以像 coq 中的函数应用一样处理 let 表达式？

编辑：

我通过将 select_perm 修改为 select_perm'

找到了临时替代解决方案

Lemma select_perm': forall x l,
   Permutation (x::l) ((fst (select x l)) :: (snd (select x l))).

并归纳列表的长度而不是列表本身（如果需要可以提供该代码），但宁愿只使用 Appel 的原始定义...

Answer 1

是的，这是一件棘手的事情。这是我建议的结构。为了做一个可行的自我示例，我只假设函数 select 和 selsort 以及关系 Permutation.

的存在

我实际上在我的目标中引入了我希望使用的定理实例（如你所建议的），然后我可以用 Heqp 重写。最后两行是实际发生的地方。

Require Import List.

Section playground.

Variable select : nat -> list nat -> nat * list nat.

Variable Permutation : list nat -> list nat -> Prop.

Lemma select_perm: forall x l,
  let (y,r) := select x l in
   Permutation (x::l) (y::r).
Proof.
Admitted.

Variable selsort : list nat -> nat -> list nat.

Lemma goal_at_hand (a : nat) (l : list nat)
  (IHl : forall n : nat, length l = n -> Permutation l (selsort l n))
  (n : nat) (l0 : list nat) (Heqp : select a l = (n, l0)):
  Permutation (a :: l) (n :: selsort l0 (length l)).
Proof.
generalize (select_perm a l).
rewrite Heqp.

这很棘手，因为 Coq 使用 let ... := ... in ... 语法，但这实际上是一个模式匹配表达式：您需要表达式明确地应用 pair 构造函数let 以更简单的形式转换自身的表达式。

您获得的目标具有以下形状，我想您需要一个引理说明 Permutation 是可传递的才能继续。

  Permutation (a :: l) (n :: l0) ->
  Permutation (a :: l) (n :: selsort l0 (length l))

在 Coq 中修改、使用和应用 let 表达式

Modifying, working with, and applying let expressions in Coq

let

coq

coq-tactic