考克 "convoy pattern"

Question

我正在尝试使用 "convoy pattern" 来保留 3 个变量（两个参数和 return 值）之间的依赖关系：

Require Import Vector.

(* "sparse" vector type *)
Notation svector A n := (Vector.t (option A) n).

Fixpoint svector_is_dense {A} {n} (v:svector A n) : Prop :=
  match v with
  | Vector.nil => True
  | Vector.cons (None) _ _ => False
  | Vector.cons (Some _) _ xs => svector_is_dense xs
  end.

Lemma svector_tl_dense {A} {n} {v: svector A (S n)}:
  svector_is_dense v -> svector_is_dense (Vector.tl v).
Admitted.

Lemma svector_hd {A} {n} (v:svector A (S n)): svector_is_dense v -> A.
Admitted.

Fixpoint vector_from_svector {A} {n} {v:svector A n} (D:svector_is_dense v): Vector.t A n :=
  match n return (svector A n) -> (svector_is_dense v) -> (Vector.t A n) with
  | O => fun _ _ => @Vector.nil A
  | (S p) => fun v0 D0 => Vector.cons
                            (svector_hd v0 D0)
                            (vector_from_svector (Vector.tl v) (svector_tl_dense D))
  end v D.

问题出现在最后一个定义中。为什么它不起作用有什么建议吗？

Answer 1

你几乎答对了。问题出在您的 return 子句中，该子句是非依赖的。你需要的是

match n return forall (w: svector A n), (svector_is_dense w) -> (Vector.t A n) with

这样 D0 就不是 svector_is_dense v 类型，而是 svector_is_dense v0.

顺便说一下，在第二个构造函数中，我猜你指的是 Vector.tl v0 和 svector_tl_dense D0。这是我写的完整术语（不要介意 cons 中的附加 _，我没有激活 implicits）：

Fixpoint vector_from_svector {A} {n} {v:svector A n} (D:svector_is_dense v): Vector.t A n :=
  match n return forall (w:svector A n), (svector_is_dense w) -> (Vector.t A n) with
  | O => fun _ _ => @Vector.nil A
  | (S p) => fun v0 D0 => Vector.cons _
                            (svector_hd v0 D0) _
                            (vector_from_svector (svector_tl_dense D0))
  end v D.

考克 "convoy pattern"

Coq "convoy pattern"

coq

dependent-type

convoy-pattern