对于 Coq 中的异构列表，可以证明等价于 Forall_inv 吗？

Question

遵循 Adam Chlipala 的 definition 异构列表，我想在普通列表上定义一个等价于 Forall 的函数。这并不太难，您最终会像往常一样得到两个构造函数。现在假设我知道关于非空列表的每个元素的事实都是正确的。对于普通列表，我可以使用 Forall_inv 和 Forall_inv_tail 断言列表的头部和尾部为真。

我想证明下面定义的 hForall 的等价性，从首例开始。查看 Lists/List.v 中的源代码，正规列表的证明很简单，并通过 Forall (a :: l) 上的反转运行。我的 hForall 的等价物给出了一堆因变量。我是否遗漏了一些明显的东西？

Require Import List.

Section hlist.
  Variable A : Type.
  Variable B : A -> Type.

  Inductive hlist : list A -> Type :=
  | HNil : hlist nil
  | HCons {a : A} {ls : list A} : B a -> hlist ls -> hlist (a :: ls).

  Section hForall.
    Variable P : forall a : A, B a -> Prop.

    Inductive hForall : forall {As : list A}, hlist As -> Prop :=
    | hForall_nil : hForall HNil
    | hForall_cons {a : A} {ls : list A} (x : B a) (hl : hlist ls)
      : P a x -> hForall hl -> hForall (HCons x hl).

    Lemma hForall_inv
          (a : A)
          (ls : list A)
          (x : B a)
          (hl : hlist ls)
      : hForall (HCons x hl) -> P a x.
    Proof.
      (* Help! *)
    Abort.
  End hForall.
End hlist.

Answer 1

由索引类型索引的归纳法导致了这种困难。

或者，考虑将 hForall 定义为 Fixpoint。然后通过展开定义来得出反演引理。

  Section hForall'.

    Variable P : forall a, B a -> Prop.

    Fixpoint hForall' {As : list A} (hs : hlist As) : Prop :=
      match hs with
      | HNil => True
      | HCons x js => P _ x /\ hForall' js
      end.

    Lemma hForall'_inv
          (a : A)
          (ls : list A)
          (x : B a)
          (hl : hlist ls)
      : hForall' (HCons x hl) -> P a x.
    Proof.
      intros []; auto.
    Qed.

  End hForall'.

附录

主要是出于教育目的，这里有一些方法可以证明hForall的原始归纳定义的逆引理（从更简单的开始）。

一种解决方案是 dependent destruction 策略，与 destruct 相反，它也可以自动处理异构等式。它是从 Program 模块导入的：

    Import Program.

    Lemma hForall_inv
          (a : A)
          (ls : list A)
          (x : B a)
          (hl : hlist ls)
      : hForall (HCons x hl) -> P a x.
    Proof.
      intros H.
      dependent destruction H.
      auto.
    Qed.

（次要的）问题是它使用了一些关于异构相等性的公理：

    Print Assumptions hForall_inv.

(*
Section Variables:
P : forall a : A, B a -> Prop
B : A -> Type
A : Type
Axioms:
Eqdep.Eq_rect_eq.eq_rect_eq : forall (U : Type) (p : U) 
                                (Q : U -> Type) (x : Q p) 
                                (h : p = p), x = eq_rect p Q x p h
JMeq_eq : forall (A : Type) (x y : A), x ~= y -> x = y
*)

随着对 destruct works/dependent 模式匹配方式的更多了解，这里是一个没有公理的证明。

在 CPDT 中有一些依赖模式匹配的详细解释，但简而言之，问题是当我们在 hForall (HCons x hl) 上执行 destruct/inversion 时，索引 HCons x hl 在 case-split 之前被泛化，所以你得到一个无意义的案例，它被替换为 HNil，第二个案例具有 different 索引 HCons x0 hl0 ，并且记住该泛化中的（异质）平等的一种好方法是研究级问题。如果目标只是用这些变量重写，你就不需要搞乱异构等式，实际上你可以重构目标，使其明确依赖于 HCons x hl，而不是 x 和 hl 分开，然后将其概括为 destruct:

    Lemma hForall_inv'
          (a : A)
          (ls : list A)
          (x : B a)
          (hl : hlist ls)
      : hForall (HCons x hl) -> P a x.
    Proof.
      intros H.

      change (match HCons x hl return Prop with  (* for some reason you have to explicitly annotate the return type as Prop right here *)
              | HNil => True
              | HCons x _ => P _ x
              end).

      destruct H.
      - exact I.  (* Replace [HCons x hl] with [HNil], the goal reduces to [True]. (This is an unreachable case.) *)
      - assumption.

    (* Or, directly writing down the proof term. *)
    Restart.
      intros H.
      refine (match H in @hForall As hs return
                    match hs return Prop with
                    | HNil => True
                    | HCons x _ => P _ x
                    end
              with
              | hForall_nil => I
              | hForall_cons _ _ _ _ => _
              end).
      assumption.
    Qed.

方程式插件可能会正确地自动化，但我还没有尝试过。

Answer 2

我认为解决这种破坏的最简单方法是告诉 Coq 我们关心这些破坏模式。或者，您可以使用记忆策略，但有时它会使您的定理更难推理。

    Lemma hForall_inv
          (a : A)
          (ls : list A)
          (x : B a)
          (hl : hlist ls)
      : hForall (HCons x hl) -> P a x.
    Proof.
      have : forall (F : forall (a : A) (ls : list A) (x : B a) (hl : hlist ls) (H : hForall (HCons x hl)), Prop), 
               (forall (a : A) (ls : list A) (x : B a) (hl : hlist ls) (H : hForall (HCons x hl)) (I : forall (a : A) (ls : list A) (x : B a) (hl : hlist ls) (f : P a x) (H : hForall (HCons x hl)), F a ls x hl H),
                   F a ls x hl H).
      intros.
      refine (match H in (hForall (HCons x hl)) return F _ _ _ _ H with 
               |hForall_nil => _
               |hForall_cons a x y z => _
             end).
      exact idProp.
      exact (I _ _ _ _ y (hForall_cons a x y z)).
      move => forall_rect. 
      elim/forall_rect; by [].
   Qed.

我正在使用 Type 进行消除的观察结果：

Inductive hForall : forall {As : list A}, hlist As -> Type :=
| hForall_nil : hForall HNil
| hForall_cons {a : A} {ls : list A} (x : B a) (hl : hlist ls)
  : P a x -> hForall hl -> hForall (HCons x hl).

对于 Coq 中的异构列表，可以证明等价于 Forall_inv 吗？

Can one prove an equivalent to Forall_inv for heterogeneous lists in Coq?

coq

dependent-type

附录