Implementing safe element retrieval by index from list in Coq

Question

I'm trying to demonstrate the difference in code generation between Coq Extraction mechanism and MAlonzo compiler in Agda. I came up with this simple example in Agda:

data Nat : Set where
  zero : Nat
  succ : Nat → Nat

data List (A : Set) : Set where
  nil : List A
  cons : A → List A → List A

length : ∀ {A} → List A → Nat
length nil = zero
length (cons _ xs) = succ (length xs)

data Fin : Nat → Set where
  finzero : ∀ {n} → Fin (succ n)
  finsucc : ∀ {n} → Fin n → Fin (succ n)

elemAt : ∀ {A} (xs : List A) → Fin (length xs) → A
elemAt nil ()
elemAt (cons x _) finzero = x
elemAt (cons _ xs) (finsucc n) = elemAt xs n

Direct translation to Coq (with absurd pattern emulation) yields:

Inductive Nat : Set :=
| zero : Nat
| succ : Nat -> Nat.

Inductive List (A : Type) : Type :=
| nil : List A
| cons : A -> List A -> List A.

Fixpoint length (A : Type) (xs : List A) {struct xs} : Nat :=
   match xs with
   | nil => zero
   | cons _ xs' => succ (length _ xs')
   end.

Inductive Fin : Nat -> Set :=
| finzero : forall n : Nat, Fin (succ n)
| finsucc : forall n : Nat, Fin n -> Fin (succ n).

Lemma finofzero : forall f : Fin zero, False.
Proof. intros a; inversion a. Qed.

Fixpoint elemAt (A : Type) (xs : List A) (n : Fin (length _ xs)) : A :=
   match xs, n with
   | nil, _ => match finofzero n with end
   | cons x _, finzero _ => x
   | cons _ xs', finsucc m n' => elemAt _ xs' n' (* fails *)
   end.

But the last case in elemAt fails with:

File "./Main.v", line 26, characters 46-48:
Error:
In environment
elemAt : forall (A : Type) (xs : List A), Fin (length A xs) -> A
A : Type
xs : List A
n : Fin (length A xs)
a : A
xs' : List A
n0 : Fin (length A (cons A a xs'))
m : Nat
n' : Fin m
The term "n'" has type "Fin m" while it is expected to have type
 "Fin (length A xs')".

It seems that Coq does not infer succ m = length A (cons A a xs'). What should I tell Coq so it would use this information? Or am I doing something completely senseless?

Unknown Unknown · Accepted Answer · 2014-05-20T14:57:06

Doing pattern matching is the equivalent of using the destruct tactic. You won't be able to prove finofzero directly using destruct.

The inversion tactic automatically generates some equations before doing what destruct does. Then it tries to do what discriminate does. The result is really messy.

Print finofzero.

To prove something like fin zero -> P you should change it to fin n -> n = zero -> P first.
To prove something like list nat -> P (more usually forall l : list nat, P l) you don't need to change it to list A -> A = nat -> P, because list's only argument is a parameter in its definition.
To prove something like S n <= 0 -> False you should change it to S n1 <= n2 -> n2 = 0 -> False first, because the first argument of <= is a parameter while the second one isn't.
In a goal f x = f y -> P (f y), to rewrite with the hypothesis you first need to change the goal to f x = z -> f y = z -> P z, and only then will you be able to rewrite with the hypothesis using induction, because the first argument of = (actually the second) is a parameter in the definition of =.

Try defining <= without parameters to see how the induction principle changes. In general, before using induction on a predicate you should make sure it's arguments are variables. Otherwise information might be lost.

Conjecture zero_succ : forall n1, zero = succ n1 -> False.
Conjecture succ_succ : forall n1 n2, succ n1 = succ n2 -> n1 = n2.

Lemma finofzero : forall n1, Fin n1 -> n1 = zero -> False.
Proof.
intros n1 f1.
destruct f1. 
intros e1.
eapply zero_succ.
eapply eq_sym.
eapply e1.
admit.
Qed.

(* Use the Show Proof command to see how the tactics manipulate the proof term. *)
Definition elemAt' : forall (A : Type) (xs : List A) (n : Nat), Fin n -> n = length A xs -> A.
Proof.
fix elemAt 2.
intros A xs.
destruct xs as [| x xs'].
intros n f e.
destruct (finofzero f e).
destruct 1.
intros e.
eapply x.
intros e.
eapply elemAt.
eapply H.
eapply succ_succ.
eapply e.
Defined.

Print elemAt'.

Definition elemAt : forall (A : Type) (xs : List A), Fin (length A xs) -> A :=
  fun A xs f => elemAt' A xs (length A xs) f eq_refl.

CPDT has more about this.

Maybe things would be clearer if at the end of a proof Coq performed eta reduction and beta/zeta reduction (wherever variables occur at most once in scope).

Implementing safe element retrieval by index from list in Coq

2 Answers