Coq can't see that the two types are the same

Question

I am trying to define a rev function on a vector, its size is built into it, and I cannot figure out how to define a rev function on it.

Here is my type definition:

Inductive vect {X : Type} : nat -> Type -> Type
  := Nil  : vect 0 X
   | Cons : forall n, X -> vect n X -> vect (S n) X
.

---

I have identified some useful functions on it:

Fixpoint app {X : Type} {n m : nat} (v1 : vect n X) (v2 : vect m X)
: vect (n + m) X :=
  match v1 with
    | Nil => v2
    | Cons _ x xs => Cons _ x (app xs v2)
  end.

Fixpoint fold_left {X Y : Type} {n : nat} (f : Y -> X -> Y) (acc : Y) (v : vect n X)
: Y :=
  match v with
    | Nil => acc
    | Cons _ x xs => fold_left f (f acc x) xs
  end.

---

And now, I want to define rev. My first preliminary was through fold_left, but it turned out to be a complete failure.

Fixpoint rev {X : Type} {n : nat} (v : @vect X n X) : @vect X n X :=
  fold_left (fun {X : Type} {k : nat} (acc : vect k X) (x : X) => x ::: acc) {{ }} v.

I do not understand the error Error: The type of this term is a product while it is expected to be a sort..

---

My second example is almost good, but Coq cannot see that "S n = (n + 1)" initially, and I don't know how to say Coq like that.

Fixpoint rev {X : Type} {n : nat} (v : @vect X n X) : @vect X n X :=
  match v in (vect n X) return (vect n X) with
    | Nil => Nil
    | Cons _ x xs => app (rev xs) {{ x }}
  end.

Mistake The term "app (rev X n0 xs) {{x}}" has type "vect (n0 + 1) X" while it is expected to have type "vect (S n0) X"

If you have any other comments in coq code, feel free to.

Answer 1

Fixpoint rev {X : Type} {n : nat} (v : @vect X n X) : @vect X n X :=
  fold_left (fun {X : Type} {k : nat} (acc : vect k X) (x : X) => Cons x acc) Nil v.

fold_left ?1 -> ?2 -> ?1, , . [Dependent] "product" - Coq . fun (X:Type) b c d => …, ?1 - Type, fun c d => … (, , ) ?, , Type, .. .

, , fold_left : , fold_left . fold_left, Nil, 0, , 0.

, , rev, , .

---

, vect (n0 + 1) X vect (S n0) X , , n0 + 1 S n0. n0 + 1 , , , , , .

, , "" . , - eq_rect, . - - .

Definition vect_eq_nat {X : Type} {m n : nat} (H : m = n) v :=
  eq_rect _ (fun k => @vect X k X) v _ H.

eq_rect , . , , , , .

Definition vect_eq_nat {X : Type} {m n : nat} : m = n -> @vect X m X -> @vect X n X.
intros.
rewrite <- H.
exact X0.
Defined.
Print vect_eq_nat.

Program .

Program Definition vect_plus_comm {X : Type} {n : nat} (v : @vect X (n+1) X) : @vect X (S n) X :=
  vect_eq_nat _ v.
Require Import Arith.
Require Import Omega.
Solve Obligation 0 using (intros; omega).

rev.

Fixpoint rev {X : Type} {n : nat} (v : @vect X n X) : @vect X n X :=
  match v in (vect n X) return (vect n X) with
    | Nil => Nil
    | Cons _ x xs => vect_plus_comm (app (rev xs) (Cons _ x Nil))
  end.

Program Fixpoint, rev , . S n0 n0 + 1.

Program Fixpoint rev' {X : Type} {n : nat} (v : @vect X n X) : @vect X n X :=
  match v in (vect n X) return (vect n X) with
    | Nil => Nil
    | Cons _ x xs => vect_eq_nat _ (app (rev' xs) (Cons _ x Nil))
  end.
Solve Obligation 0 using (intros; omega).