Exercise session 6 — Dependent functional programming — Solutions
- Files:
Set Default Goal Selector "!". From Stdlib Require Import Arith List Lia. Import ListNotations. From Equations Require Import Equations.
Exercise: Decidable equality for nat
Define a Boolean equality test using Equations.
Exercise: Specification of eq_nat
Prove the following two lemmas specifying your eq_nat using funelim.
n, m: nateq_nat n m = true -> n = mn, m: nateq_nat n m = true -> n = mn, m: nat
h: eq_nat n m = truen = mh: eq_nat 0 0 = true
Heqcall: true = eq_nat 0 00 = 0n: nat
h: eq_nat 0 (S n) = true
Heqcall: false = eq_nat 0 (S n)0 = S nn: nat
h: eq_nat (S n) 0 = true
Heqcall: false = eq_nat (S n) 0S n = 0n, m: nat
H: forall n0 m0 : nat, eq_nat n0 m0 = true -> {| pr1 := n; pr2 := m |} = {| pr1 := n0; pr2 := m0 |} -> eq_nat n m = eq_nat n0 m0 -> n0 = m0
h: eq_nat (S n) (S m) = true
Heqcall: eq_nat n m = eq_nat (S n) (S m)S n = S mn, m: nat
H: forall n0 m0 : nat, eq_nat n0 m0 = true -> {| pr1 := n; pr2 := m |} = {| pr1 := n0; pr2 := m0 |} -> eq_nat n m = eq_nat n0 m0 -> n0 = m0
h: eq_nat (S n) (S m) = true
Heqcall: eq_nat n m = eq_nat (S n) (S m)S n = S mn, m: nat
H: forall n0 m0 : nat, eq_nat n0 m0 = true -> {| pr1 := n; pr2 := m |} = {| pr1 := n0; pr2 := m0 |} -> eq_nat n m = eq_nat n0 m0 -> n0 = m0
h: eq_nat (S n) (S m) = true
Heqcall: eq_nat n m = eq_nat (S n) (S m)n = mall: congruence. Qed.n, m: nat
H: forall n0 m0 : nat, eq_nat n0 m0 = true -> {| pr1 := n; pr2 := m |} = {| pr1 := n0; pr2 := m0 |} -> eq_nat n m = eq_nat n0 m0 -> n0 = m0
h: eq_nat (S n) (S m) = true
Heqcall: eq_nat n m = eq_nat (S n) (S m)eq_nat n m = truen, m: nat
H: forall n0 m0 : nat, eq_nat n0 m0 = true -> {| pr1 := n; pr2 := m |} = {| pr1 := n0; pr2 := m0 |} -> eq_nat n m = eq_nat n0 m0 -> n0 = m0
h: eq_nat (S n) (S m) = true
Heqcall: eq_nat n m = eq_nat (S n) (S m){| pr1 := n; pr2 := m |} = {| pr1 := n; pr2 := m |}n, m: nat
H: forall n0 m0 : nat, eq_nat n0 m0 = true -> {| pr1 := n; pr2 := m |} = {| pr1 := n0; pr2 := m0 |} -> eq_nat n m = eq_nat n0 m0 -> n0 = m0
h: eq_nat (S n) (S m) = true
Heqcall: eq_nat n m = eq_nat (S n) (S m)eq_nat n m = eq_nat n mn, m: nateq_nat n m = false -> n <> mn, m: nateq_nat n m = false -> n <> mn, m: nat
h: eq_nat n m = falsen <> mh: eq_nat 0 0 = false
Heqcall: true = eq_nat 0 00 <> 0n: nat
h: eq_nat 0 (S n) = false
Heqcall: false = eq_nat 0 (S n)0 <> S nn: nat
h: eq_nat (S n) 0 = false
Heqcall: false = eq_nat (S n) 0S n <> 0n, m: nat
H: forall n0 m0 : nat, eq_nat n0 m0 = false -> {| pr1 := n; pr2 := m |} = {| pr1 := n0; pr2 := m0 |} -> eq_nat n m = eq_nat n0 m0 -> n0 <> m0
h: eq_nat (S n) (S m) = false
Heqcall: eq_nat n m = eq_nat (S n) (S m)S n <> S mn, m: nat
H: forall n0 m0 : nat, eq_nat n0 m0 = false -> {| pr1 := n; pr2 := m |} = {| pr1 := n0; pr2 := m0 |} -> eq_nat n m = eq_nat n0 m0 -> n0 <> m0
h: eq_nat (S n) (S m) = false
Heqcall: eq_nat n m = eq_nat (S n) (S m)S n <> S mn, m: nat
H: forall n0 m0 : nat, eq_nat n0 m0 = false -> {| pr1 := n; pr2 := m |} = {| pr1 := n0; pr2 := m0 |} -> eq_nat n m = eq_nat n0 m0 -> n0 <> m0
h: eq_nat (S n) (S m) = false
Heqcall: eq_nat n m = eq_nat (S n) (S m)
e: S n = S mFalsem: nat
Heqcall: eq_nat m m = eq_nat (S m) (S m)
h: eq_nat (S m) (S m) = false
H: forall n m0 : nat, eq_nat n m0 = false -> {| pr1 := m; pr2 := m |} = {| pr1 := n; pr2 := m0 |} -> eq_nat m m = eq_nat n m0 -> n <> m0Falsem: nat
Heqcall: eq_nat m m = eq_nat (S m) (S m)
h: eq_nat m m = false
H: forall n m0 : nat, eq_nat n m0 = false -> {| pr1 := m; pr2 := m |} = {| pr1 := n; pr2 := m0 |} -> eq_nat m m = eq_nat n m0 -> n <> m0Falseall: eauto. Qed.m: nat
Heqcall: eq_nat m m = eq_nat (S m) (S m)
h: eq_nat m m = false
H: forall n m0 : nat, eq_nat n m0 = false -> {| pr1 := m; pr2 := m |} = {| pr1 := n; pr2 := m0 |} -> eq_nat m m = eq_nat n m0 -> n <> m0eq_nat ?n ?m = falsem: nat
Heqcall: eq_nat m m = eq_nat (S m) (S m)
h: eq_nat m m = false
H: forall n m0 : nat, eq_nat n m0 = false -> {| pr1 := m; pr2 := m |} = {| pr1 := n; pr2 := m0 |} -> eq_nat m m = eq_nat n m0 -> n <> m0{| pr1 := m; pr2 := m |} = {| pr1 := ?n; pr2 := ?m |}m: nat
Heqcall: eq_nat m m = eq_nat (S m) (S m)
h: eq_nat m m = false
H: forall n m0 : nat, eq_nat n m0 = false -> {| pr1 := m; pr2 := m |} = {| pr1 := n; pr2 := m0 |} -> eq_nat m m = eq_nat n m0 -> n <> m0eq_nat m m = eq_nat ?n ?mm: nat
Heqcall: eq_nat m m = eq_nat (S m) (S m)
h: eq_nat m m = false
H: forall n m0 : nat, eq_nat n m0 = false -> {| pr1 := m; pr2 := m |} = {| pr1 := n; pr2 := m0 |} -> eq_nat m m = eq_nat n m0 -> n <> m0?n = ?m
Exercise: Convoy pattern
Sometimes it is useful to remember an expression that we "destruct".
For instance, in the proof of eq_dec below, destruct (eq_nat n m) eqn: e
remembers the equation e between eq_nat n m and the value it is
destructed into.
Can you do the same using only match, by defining eq_dec_term?
forall n m : nat, {n = m} + {n <> m}forall n m : nat, {n = m} + {n <> m}n, m: nat{n = m} + {n <> m}n, m: nat
e: eq_nat n m = true{n = m} + {n <> m}n, m: nat
e: eq_nat n m = false{n = m} + {n <> m}n, m: nat
e: eq_nat n m = true{n = m} + {n <> m}n, m: nat
e: eq_nat n m = truen = massumption.n, m: nat
e: eq_nat n m = trueeq_nat n m = truen, m: nat
e: eq_nat n m = false{n = m} + {n <> m}n, m: nat
e: eq_nat n m = falsen <> massumption. Qed. Definition eq_dec_term (n m : nat) : { n = m } + { n <> m } := match eq_nat n m as x return eq_nat n m = x -> _ with | true => fun e => left (eq_nat_eq e) | false => fun e => right (neq_nat_neq e) end eq_refl. (* From the lecture: *) Inductive vec (A : Type) : nat -> Type := | vnil : vec A 0 | vcons (a : A) (n : nat) (v : vec A n) : vec A (S n). Arguments vnil {A}. Arguments vcons {A} a {n}.n, m: nat
e: eq_nat n m = falseeq_nat n m = false
Exercise: Head and tail of vectors
Define the head and tail functions on vectors manually by filling the gaps
in the following programs.
You have to use the return clause and the vnil branch explicitly.
Definition hd {A n} (v : vec A (S n)) : A := match v in vec _ m return match m with | 0 => unit | S k => A end with | vnil => tt | vcons a v => a end. Definition tl {A n} (v : vec A (S n)) : vec A n := match v in vec _ m return match m with | 0 => unit | S k => vec A k end with | vnil => tt | vcons a v => v end.
Exercise: zip by hand
Define the zip function by hand, using Fixpoint and match (we call it
zip' to avoid a clash with the definition from the lecture notes).
Fixpoint zip' {A B n} (v : vec A n) (w : vec B n) : vec (A * B) n := match v in vec _ m return vec B m -> vec (A * B) m with | vnil => fun _ => vnil | vcons a v => fun w => vcons (a, hd w) (zip' v (tl w)) end w. (* From the lecture: *) Inductive fin : nat -> Type := | fin0 n : fin (S n) | finS n (x : fin n) : fin (S n). Arguments fin0 {n}. Arguments finS {n}.
Exercise: Repeat
Define repeat such that repeat a n is a vector of length n with all
elements equal to a.
Give and prove its functional elimination principle.
Then use it to prove the associated lemma.
You can compare with the proof using funelim.
forall (A : Type) (a : A) (P : forall n : nat, vec A n -> Prop), P 0 vnil -> (forall n : nat, P n (repeat a n) -> P (S n) (vcons a (repeat a n))) -> forall n : nat, P n (repeat a n)forall (A : Type) (a : A) (P : forall n : nat, vec A n -> Prop), P 0 vnil -> (forall n : nat, P n (repeat a n) -> P (S n) (vcons a (repeat a n))) -> forall n : nat, P n (repeat a n)A: Type
a: A
P: forall n : nat, vec A n -> Prop
hnil: P 0 vnil
hcons: forall n : nat, P n (repeat a n) -> P (S n) (vcons a (repeat a n))
n: natP n (repeat a n)A: Type
a: A
P: forall n : nat, vec A n -> Prop
hnil: P 0 vnil
hcons: forall n : nat, P n (repeat a n) -> P (S n) (vcons a (repeat a n))P 0 (repeat a 0)A: Type
a: A
P: forall n : nat, vec A n -> Prop
hnil: P 0 vnil
hcons: forall n : nat, P n (repeat a n) -> P (S n) (vcons a (repeat a n))
n: nat
IHn: P n (repeat a n)P (S n) (repeat a (S n))apply hnil.A: Type
a: A
P: forall n : nat, vec A n -> Prop
hnil: P 0 vnil
hcons: forall n : nat, P n (repeat a n) -> P (S n) (vcons a (repeat a n))P 0 (repeat a 0)A: Type
a: A
P: forall n : nat, vec A n -> Prop
hnil: P 0 vnil
hcons: forall n : nat, P n (repeat a n) -> P (S n) (vcons a (repeat a n))
n: nat
IHn: P n (repeat a n)P (S n) (repeat a (S n))assumption. Qed.A: Type
a: A
P: forall n : nat, vec A n -> Prop
hnil: P 0 vnil
hcons: forall n : nat, P n (repeat a n) -> P (S n) (vcons a (repeat a n))
n: nat
IHn: P n (repeat a n)P n (repeat a n)A: Type
a: A
n: nat
m: fin nvnth (repeat a n) m = aA: Type
a: A
n: nat
m: fin nvnth (repeat a n) m = aA: Type
a: A
n: natforall m : fin n, vnth (repeat a n) m = aA: Type
a: A
n: nat(fun (n0 : nat) (v : vec A n0) => forall m : fin n0, vnth v m = a) n (repeat a n)A: Type
a: A
n: natforall m : fin 0, vnth vnil m = aA: Type
a: A
n: natforall n0 : nat, (forall m : fin n0, vnth (repeat a n0) m = a) -> forall m : fin (S n0), vnth (vcons a (repeat a n0)) m = aA: Type
a: A
n: natforall m : fin 0, vnth vnil m = adependent elimination m.A: Type
a: A
n: nat
m: fin 0vnth vnil m = aA: Type
a: A
n: natforall n0 : nat, (forall m : fin n0, vnth (repeat a n0) m = a) -> forall m : fin (S n0), vnth (vcons a (repeat a n0)) m = aA: Type
a: A
n, m: nat
ih: forall m0 : fin m, vnth (repeat a m) m0 = a
k: fin (S m)vnth (vcons a (repeat a m)) k = aA: Type
a: A
n, n0: nat
ih: forall m : fin n0, vnth (repeat a n0) m = avnth (vcons a (repeat a n0)) fin0 = aA: Type
a: A
n, n1: nat
ih: forall m : fin n1, vnth (repeat a n1) m = a
x: fin n1vnth (vcons a (repeat a n1)) (finS x) = aA: Type
a: A
n, n0: nat
ih: forall m : fin n0, vnth (repeat a n0) m = avnth (vcons a (repeat a n0)) fin0 = areflexivity.A: Type
a: A
n, n0: nat
ih: forall m : fin n0, vnth (repeat a n0) m = aa = asimp vnth. Abort.A: Type
a: A
n, n1: nat
ih: forall m : fin n1, vnth (repeat a n1) m = a
x: fin n1vnth (vcons a (repeat a n1)) (finS x) = a
The proof is easier with funelim.
A: Type
a: A
n: nat
m: fin nvnth (repeat a n) m = aA: Type
a: A
n: nat
m: fin nvnth (repeat a n) m = aA: Type
a: A
m: fin 0
Heqcall: vnil = repeat a 0vnth vnil m = aA: Type
a: A
n: nat
H: forall m : fin n, vnth (repeat a n) m = a
m: fin (S n)
Heqcall: vcons a (repeat a n) = repeat a (S n)vnth (vcons a (repeat a n)) m = adependent elimination m.A: Type
a: A
m: fin 0
Heqcall: vnil = repeat a 0vnth vnil m = aA: Type
a: A
n: nat
H: forall m : fin n, vnth (repeat a n) m = a
m: fin (S n)
Heqcall: vcons a (repeat a n) = repeat a (S n)vnth (vcons a (repeat a n)) m = aA: Type
a: A
n0: nat
H: forall m : fin n0, vnth (repeat a n0) m = a
Heqcall: vcons a (repeat a n0) = repeat a (S n0)vnth (vcons a (repeat a n0)) fin0 = aA: Type
a: A
n1: nat
H: forall m : fin n1, vnth (repeat a n1) m = a
x: fin n1
Heqcall: vcons a (repeat a n1) = repeat a (S n1)vnth (vcons a (repeat a n1)) (finS x) = aA: Type
a: A
n0: nat
H: forall m : fin n0, vnth (repeat a n0) m = a
Heqcall: vcons a (repeat a n0) = repeat a (S n0)vnth (vcons a (repeat a n0)) fin0 = areflexivity.A: Type
a: A
n0: nat
H: forall m : fin n0, vnth (repeat a n0) m = a
Heqcall: vcons a (repeat a n0) = repeat a (S n0)a = asimp vnth. Qed.A: Type
a: A
n1: nat
H: forall m : fin n1, vnth (repeat a n1) m = a
x: fin n1
Heqcall: vcons a (repeat a n1) = repeat a (S n1)vnth (vcons a (repeat a n1)) (finS x) = a
Exercise: Map
Same thing with a map function vmap on vectors: define it and prove
that vnth (vmap f v) x is equal to something not mentioning vmap.
State and prove the functional elimination principle for vmap.
A, B: Type
n: nat
f: A -> B
v: vec A n
m: fin nvnth (vmap f v) m = f (vnth v m)A, B: Type
n: nat
f: A -> B
v: vec A n
m: fin nvnth (vmap f v) m = f (vnth v m)A, B: Type
f: A -> B
m: fin 0
Heqcall: vnil = vmap f vnilvnth vnil m = f (vnth vnil m)A, B: Type
n0: nat
f: A -> B
a: A
v: vec A n0
H: forall m : fin n0, vnth (vmap f v) m = f (vnth v m)
m: fin (S n0)
Heqcall: vcons (f a) (vmap f v) = vmap f (vcons a v)vnth (vcons (f a) (vmap f v)) m = f (vnth (vcons a v) m)A, B: Type
f: A -> B
m: fin 0
Heqcall: vnil = vmap f vnilvnth vnil m = f (vnth vnil m)dependent elimination m.A, B: Type
f: A -> B
m: fin 0
Heqcall: vnil = vmap f vnilvnth vnil m = f (vnth vnil m)A, B: Type
n0: nat
f: A -> B
a: A
v: vec A n0
H: forall m : fin n0, vnth (vmap f v) m = f (vnth v m)
m: fin (S n0)
Heqcall: vcons (f a) (vmap f v) = vmap f (vcons a v)vnth (vcons (f a) (vmap f v)) m = f (vnth (vcons a v) m)A, B: Type
n0: nat
f: A -> B
a: A
v: vec A n0
H: forall m : fin n0, vnth (vmap f v) m = f (vnth v m)
m: fin (S n0)
Heqcall: vcons (f a) (vmap f v) = vmap f (vcons a v)vnth (vcons (f a) (vmap f v)) m = f (vnth (vcons a v) m)A, B: Type
n: nat
f: A -> B
a: A
v: vec A n
H: forall m : fin n, vnth (vmap f v) m = f (vnth v m)
Heqcall: vcons (f a) (vmap f v) = vmap f (vcons a v)vnth (vcons (f a) (vmap f v)) fin0 = f (vnth (vcons a v) fin0)A, B: Type
n1: nat
f: A -> B
a: A
v: vec A n1
H: forall m : fin n1, vnth (vmap f v) m = f (vnth v m)
x: fin n1
Heqcall: vcons (f a) (vmap f v) = vmap f (vcons a v)vnth (vcons (f a) (vmap f v)) (finS x) = f (vnth (vcons a v) (finS x))A, B: Type
n: nat
f: A -> B
a: A
v: vec A n
H: forall m : fin n, vnth (vmap f v) m = f (vnth v m)
Heqcall: vcons (f a) (vmap f v) = vmap f (vcons a v)vnth (vcons (f a) (vmap f v)) fin0 = f (vnth (vcons a v) fin0)reflexivity.A, B: Type
n: nat
f: A -> B
a: A
v: vec A n
H: forall m : fin n, vnth (vmap f v) m = f (vnth v m)
Heqcall: vcons (f a) (vmap f v) = vmap f (vcons a v)f a = f asimp vnth. Qed.A, B: Type
n1: nat
f: A -> B
a: A
v: vec A n1
H: forall m : fin n1, vnth (vmap f v) m = f (vnth v m)
x: fin n1
Heqcall: vcons (f a) (vmap f v) = vmap f (vcons a v)vnth (vcons (f a) (vmap f v)) (finS x) = f (vnth (vcons a v) (finS x))A, B: Type
f: A -> B
P: forall n : nat, vec A n -> vec B n -> PropP 0 vnil vnil -> (forall (a : A) (n : nat) (v : vec A n), P n v (vmap f v) -> P (S n) (vcons a v) (vcons (f a) (vmap f v))) -> forall (n : nat) (v : vec A n), P n v (vmap f v)A, B: Type
f: A -> B
P: forall n : nat, vec A n -> vec B n -> PropP 0 vnil vnil -> (forall (a : A) (n : nat) (v : vec A n), P n v (vmap f v) -> P (S n) (vcons a v) (vcons (f a) (vmap f v))) -> forall (n : nat) (v : vec A n), P n v (vmap f v)A, B: Type
f: A -> B
P: forall n : nat, vec A n -> vec B n -> Prop
h0: P 0 vnil vnil
hS: forall (a : A) (n : nat) (v : vec A n), P n v (vmap f v) -> P (S n) (vcons a v) (vcons (f a) (vmap f v))
n: nat
v: vec A nP n v (vmap f v)A, B: Type
f: A -> B
P: forall n : nat, vec A n -> vec B n -> Prop
h0: P 0 vnil vnil
hS: forall (a : A) (n : nat) (v : vec A n), P n v (vmap f v) -> P (S n) (vcons a v) (vcons (f a) (vmap f v))P 0 vnil (vmap f vnil)A, B: Type
f: A -> B
P: forall n : nat, vec A n -> vec B n -> Prop
h0: P 0 vnil vnil
hS: forall (a : A) (n : nat) (v : vec A n), P n v (vmap f v) -> P (S n) (vcons a v) (vcons (f a) (vmap f v))
a: A
n: nat
v: vec A n
IHv: P n v (vmap f v)P (S n) (vcons a v) (vmap f (vcons a v))apply h0.A, B: Type
f: A -> B
P: forall n : nat, vec A n -> vec B n -> Prop
h0: P 0 vnil vnil
hS: forall (a : A) (n : nat) (v : vec A n), P n v (vmap f v) -> P (S n) (vcons a v) (vcons (f a) (vmap f v))P 0 vnil (vmap f vnil)A, B: Type
f: A -> B
P: forall n : nat, vec A n -> vec B n -> Prop
h0: P 0 vnil vnil
hS: forall (a : A) (n : nat) (v : vec A n), P n v (vmap f v) -> P (S n) (vcons a v) (vcons (f a) (vmap f v))
a: A
n: nat
v: vec A n
IHv: P n v (vmap f v)P (S n) (vcons a v) (vmap f (vcons a v))assumption. Qed.A, B: Type
f: A -> B
P: forall n : nat, vec A n -> vec B n -> Prop
h0: P 0 vnil vnil
hS: forall (a : A) (n : nat) (v : vec A n), P n v (vmap f v) -> P (S n) (vcons a v) (vcons (f a) (vmap f v))
a: A
n: nat
v: vec A n
IHv: P n v (vmap f v)P n v (vmap f v)
Exercise: Reversing a vector
Can you fix the definition of rev_acc below that is supposed to reverse a
vector by using an accumulator?
It should work when removing the Fail.
Definition transport {A} {P : A -> Type} {u v} (e : u = v) : P u -> P v := match e with | eq_refl => fun x => x end.
Exercise: Vectors as subset types
We could also define vectors by using subset types, as we show below.
Define the head and tail functions again for ilist.
Definition ilist (A : Type) (n : nat) :=
{ l : list A | length l = n }.Some notations so that it's nicer:
Notation "⟨ u | v ⟩" := (exist _ u v) (at level 0). Notation "⟨ u ⟩" := (⟨ u | _ ⟩) (at level 0, only parsing).(* From the lecture: *) Inductive type := tunit | tarrow (a b : type). Notation "A ~> B" := (tarrow A B) (at level 20, right associativity). Definition env := vec type. Inductive term {n} (E : env n) : type -> Type := | tvar (x : fin n) : term E (vnth E x) | tstar : term E tunit | tlam (A : type) B (b : term (vcons A E) B) : term E (A ~> B) | tapp A B (f : term E (A ~> B)) (u : term E A) : term E B. Arguments tvar {n E}. Arguments tstar {n E}. Arguments tlam {n E} A {B}. Arguments tapp {n E A B}. Definition test A B : term vnil _ := tlam (A ~> B) ( tlam A ( tapp (tvar (E := vcons _ (vcons _ _)) (finS fin0)) (tvar fin0) ) ). Set Equations Transparent.
Exercise: Normal forms
To practice dependent elimination a bit more, we give you a new definition of terms of the simply typed λ-calculus, but this time with a dichotomy between normal terms that are values and those that are "stuck".
Show that a normal term of type tunit ~> tunit in the empty environment is
necessarily a λ, meaning some nlam.
Arguments svar {n E}. Arguments nstar {n E}. Arguments nlam {n E} A {B}. Arguments sapp {n E A B}. Arguments nstuck {n E A}.Definition isnil {A n} (v : vec A n) := match v with | vnil => True | _ => False end.n: nat
E: env n
A: typeisnil E -> stuck E A -> Falsen: nat
E: env n
A: typeisnil E -> stuck E A -> Falsen: nat
E: env n
A: type
h: isnil E
s: stuck E AFalsen: nat
E: env n
h: isnil E
x: fin nFalsen: nat
E: env n
h: isnil E
A, B: type
s: stuck E (A ~> B)
u: normal E A
IHs: isnil E -> FalseFalsen: nat
E: env n
h: isnil E
x: fin nFalseE: env 0
h: isnil E
x: fin 0Falsen: nat
E: env (S n)
h: isnil E
x: fin (S n)Falsedependent elimination x.E: env 0
h: isnil E
x: fin 0Falsen: nat
E: env (S n)
h: isnil E
x: fin (S n)Falsecontradiction.n0: nat
a: type
v: vec type n0
h: isnil (vcons a v)
x: fin (S n0)Falseeauto. Qed.n: nat
E: env n
h: isnil E
A, B: type
s: stuck E (A ~> B)
u: normal E A
IHs: isnil E -> FalseFalseforall t : normal vnil (tunit ~> tunit), exists b : normal (vcons tunit vnil) tunit, t = nlam tunit bforall t : normal vnil (tunit ~> tunit), exists b : normal (vcons tunit vnil) tunit, t = nlam tunit bt: normal vnil (tunit ~> tunit)exists b : normal (vcons tunit vnil) tunit, t = nlam tunit bb: normal (vcons tunit vnil) tunitexists b0 : normal (vcons tunit vnil) tunit, nlam tunit b = nlam tunit b0s: stuck vnil (tunit ~> tunit)exists b : normal (vcons tunit vnil) tunit, s = nlam tunit beauto.b: normal (vcons tunit vnil) tunitexists b0 : normal (vcons tunit vnil) tunit, nlam tunit b = nlam tunit b0s: stuck vnil (tunit ~> tunit)exists b : normal (vcons tunit vnil) tunit, s = nlam tunit bs: stuck vnil (tunit ~> tunit)Falses: FalseFalses: stuck vnil (tunit ~> tunit)isnil vnilconstructor. Qed.s: stuck vnil (tunit ~> tunit)isnil vnil
Exercise: Vectors and subset types are equivalent
Show that vec A n and ilist A n are equivalent.
You may use the K axiom to prove lemma ilist_eq but it is not strictly
necessary.
Axiom K : forall A (u : A) (e : u = u), e = eq_refl.forall (A : Type) (n : nat) (l l' : ilist A n), proj1_sig l = proj1_sig l' -> l = l'forall (A : Type) (n : nat) (l l' : ilist A n), proj1_sig l = proj1_sig l' -> l = l'A: Type
n: nat
l: list A
e: length l = n
l': list A
e': length l' = n
h: proj1_sig ⟨ l | e ⟩ = proj1_sig ⟨ l' | e' ⟩⟨ l | e ⟩ = ⟨ l' | e' ⟩A: Type
n: nat
l: list A
e: length l = n
l': list A
e': length l' = n
h: l = l'⟨ l | e ⟩ = ⟨ l' | e' ⟩A: Type
n: nat
l: list A
e, e': length l = n⟨ l | e ⟩ = ⟨ l | e' ⟩A: Type
n: nat
l: list A
e, e': length l = ne = e'apply K. Qed. Record equiv (A B : Type) := { l_to_r : A -> B ; r_to_l : B -> A ; l_to_l : forall a, r_to_l (l_to_r a) = a ; r_to_r : forall b, l_to_r (r_to_l b) = b }. Fixpoint to_list {A n} (v : vec A n) : list A := match v with | vnil => [] | vcons a v => a :: to_list v end.A: Type
l: list A
e: length l = length le = eq_reflforall (A : Type) (n : nat) (v : vec A n), length (to_list v) = nforall (A : Type) (n : nat) (v : vec A n), length (to_list v) = nA: Type
n: nat
v: vec A nlength (to_list v) = nA: Typelength (to_list vnil) = 0A: Type
a: A
n: nat
v: vec A n
ih: length (to_list v) = nlength (to_list (vcons a v)) = S nreflexivity.A: Typelength (to_list vnil) = 0exact (f_equal S ih). Defined.A: Type
a: A
n: nat
v: vec A n
ih: length (to_list v) = nlength (to_list (vcons a v)) = S n
From K we can eliminate useless transports.
forall (A : Type) (u : A) (e : u = u) (P : A -> Type) (t : P u), transport e t = tforall (A : Type) (u : A) (e : u = u) (P : A -> Type) (t : P u), transport e t = tA: Type
u: A
e: u = u
P: A -> Type
t: P utransport e t = treflexivity. Qed.A: Type
u: A
e: u = u
P: A -> Type
t: P utransport eq_refl t = t
Now we prove that transport commutes with vcons.
forall (A : Type) (n m : nat) (e : S n = S m) (e' : n = m) (a : A) (v : vec A n), transport e (vcons a v) = vcons a (transport e' v)forall (A : Type) (n m : nat) (e : S n = S m) (e' : n = m) (a : A) (v : vec A n), transport e (vcons a v) = vcons a (transport e' v)A: Type
n, m: nat
e: S n = S m
e': n = m
a: A
v: vec A ntransport e (vcons a v) = vcons a (transport e' v)A: Type
n: nat
e: S n = S n
a: A
v: vec A ntransport e (vcons a v) = vcons a (transport eq_refl v)A: Type
n: nat
e: S n = S n
a: A
v: vec A ntransport e (vcons a v) = vcons a vreflexivity. Qed.A: Type
n: nat
e: S n = S n
a: A
v: vec A nvcons a v = vcons a vforall (A : Type) (n : nat), equiv (vec A n) (ilist A n)forall (A : Type) (n : nat), equiv (vec A n) (ilist A n)A: Type
n: natequiv (vec A n) (ilist A n)A: Type
n: nat
v: vec A nlength (to_list v) = nA: Type
n: nat
pat: {l : list A | length l = n}
l: list A
e: (fun l : list A => length l = n) llength l = nA: Type
n: natforall a : vec A n, transport ?Goal0@{pat:=⟨ to_list a | ?Goal@{v:=a} ⟩; l:=to_list a; e:=?Goal@{v:=a}} (to_vec (to_list a)) = aA: Type
n: natforall b : {l : list A | length l = n}, ⟨ to_list (let '⟨ l | e ⟩ := b in transport ?Goal0@{pat:=b} (to_vec l)) | ?Goal@{v:=let '⟨ l | e ⟩ := b in transport ?Goal0@{pat:=b} (to_vec l)} ⟩ = bapply length_to_list.A: Type
n: nat
v: vec A nlength (to_list v) = napply e.A: Type
n: nat
pat: {l : list A | length l = n}
l: list A
e: (fun l : list A => length l = n) llength l = nA: Type
n: natforall a : vec A n, transport (length_to_list A n a) (to_vec (to_list a)) = aA: Type
n: nat
v: vec A ntransport (length_to_list A n v) (to_vec (to_list v)) = vA: Typetransport (length_to_list A 0 vnil) (to_vec (to_list vnil)) = vnilA: Type
a: A
n: nat
v: vec A n
ih: transport (length_to_list A n v) (to_vec (to_list v)) = vtransport (length_to_list A (S n) (vcons a v)) (to_vec (to_list (vcons a v))) = vcons a vA: Typetransport (length_to_list A 0 vnil) (to_vec (to_list vnil)) = vnilreflexivity.A: Typevnil = vnilA: Type
a: A
n: nat
v: vec A n
ih: transport (length_to_list A n v) (to_vec (to_list v)) = vtransport (length_to_list A (S n) (vcons a v)) (to_vec (to_list (vcons a v))) = vcons a vA: Type
a: A
n: nat
v: vec A n
ih: transport (length_to_list A n v) (to_vec (to_list v)) = vtransport (f_equal S (length_to_list A n v)) (vcons a (to_vec (to_list v))) = vcons a vA: Type
a: A
n: nat
v: vec A n
ih: transport (length_to_list A n v) (to_vec (to_list v)) = vtransport (f_equal S (length_to_list A n v)) (vcons a (to_vec (to_list v))) = vcons a vA: Type
a: A
n: nat
v: vec A n
ih: transport (length_to_list A n v) (to_vec (to_list v)) = vvcons a (transport ?e' (to_vec (to_list v))) = vcons a veassumption.A: Type
a: A
n: nat
v: vec A n
ih: transport (length_to_list A n v) (to_vec (to_list v)) = vtransport ?e' (to_vec (to_list v)) = vA: Type
n: natforall b : {l : list A | length l = n}, ⟨ to_list (let '⟨ l | e ⟩ := b in transport e (to_vec l)) | length_to_list A n (let '⟨ l | e ⟩ := b in transport e (to_vec l)) ⟩ = bA: Type
n: nat
l: list A
e: length l = n⟨ to_list (transport e (to_vec l)) | length_to_list A n (transport e (to_vec l)) ⟩ = ⟨ l | e ⟩A: Type
n: nat
l: list A
e: length l = nproj1_sig ⟨ to_list (transport e (to_vec l)) | length_to_list A n (transport e (to_vec l)) ⟩ = proj1_sig ⟨ l | e ⟩A: Type
n: nat
l: list A
e: length l = nto_list (transport e (to_vec l)) = lA: Type
l: list Ato_list (transport eq_refl (to_vec l)) = lA: Type
l: list Ato_list (to_vec l) = lA: Type
Heqcall: vnil = to_vec []to_list vnil = []A: Type
a: A
l: list A
H: to_list (to_vec l) = l
Heqcall: vcons a (to_vec l) = to_vec (a :: l)to_list (vcons a (to_vec l)) = a :: lreflexivity.A: Type
Heqcall: vnil = to_vec []to_list vnil = []A: Type
a: A
l: list A
H: to_list (to_vec l) = l
Heqcall: vcons a (to_vec l) = to_vec (a :: l)to_list (vcons a (to_vec l)) = a :: lA: Type
a: A
l: list A
H: to_list (to_vec l) = l
Heqcall: vcons a (to_vec l) = to_vec (a :: l)to_list (vcons a (to_vec l)) = a :: lA: Type
a: A
l: list A
H: to_list (to_vec l) = l
Heqcall: vcons a (to_vec l) = to_vec (a :: l)a :: to_list (to_vec l) = a :: lassumption. Defined.A: Type
a: A
l: list A
H: to_list (to_vec l) = l
Heqcall: vcons a (to_vec l) = to_vec (a :: l)to_list (to_vec l) = l
Exercise: Normalisation by evaluation
Back to λ-calculus. This time we're going to see how we can go from the term
representation of the lecture to the normal one of the exercise above.
This method is called Normalisation by Evaluation (NbE).
We give you some definitions about renamings, which are remappings of variables.
Definition ren {n m} (E : env n) (F : env m) := { f : fin n -> fin m | forall x, vnth E x = vnth F (f x) }.n, m: nat
E: env n
F: env m
A: type
r: fin n -> fin m
e: forall x : fin n, vnth E x = vnth F (r x)
x: fin (S n)fin (S m)n, m: nat
E: env n
F: env m
A: type
r: fin n -> fin m
e: forall x : fin n, vnth E x = vnth F (r x)
x: fin (S n)vnth (vcons A E) x = vnth (vcons A F) ?Goaln, m: nat
E: env n
F: env m
A: type
r: fin n -> fin m
e: forall x : fin n, vnth E x = vnth F (r x)
x: fin (S n)fin (S m)n, m: nat
E: env n
F: env m
A: type
r: fin n -> fin m
e: forall x : fin n, vnth E x = vnth F (r x)
x: fin (S n)vnth (vcons A E) x = vnth (vcons A F) ?Goaln, m: nat
E: env n
F: env m
A: type
r: fin n -> fin m
e: forall x : fin n, vnth E x = vnth F (r x)
x: fin (S n)fin (S m)n0, m: nat
E: env n0
F: env m
A: type
r: fin n0 -> fin m
e: forall x : fin n0, vnth E x = vnth F (r x)fin (S m)n1, m: nat
E: env n1
F: env m
A: type
r: fin n1 -> fin m
e: forall x : fin n1, vnth E x = vnth F (r x)
x: fin n1fin (S m)apply fin0.n0, m: nat
E: env n0
F: env m
A: type
r: fin n0 -> fin m
e: forall x : fin n0, vnth E x = vnth F (r x)fin (S m)apply finS, r, x.n1, m: nat
E: env n1
F: env m
A: type
r: fin n1 -> fin m
e: forall x : fin n1, vnth E x = vnth F (r x)
x: fin n1fin (S m)n, m: nat
E: env n
F: env m
A: type
r: fin n -> fin m
e: forall x : fin n, vnth E x = vnth F (r x)
x: fin (S n)vnth (vcons A E) x = vnth (vcons A F) (match x in fin n0 return n0 = S n -> fin (S m) with | @fin0 n0 => apply_noConfusion (S n0) (S n) (fun H : n0 = n => DepElim.solution_left n fin0 n0 H) | @finS n0 x0 => apply_noConfusion (S n0) (S n) (fun H : n0 = n => DepElim.solution_left n (fun x1 : fin n => finS (r x1)) n0 H x0) end eq_refl)n0, m: nat
E: env n0
F: env m
A: type
r: fin n0 -> fin m
e: forall x : fin n0, vnth E x = vnth F (r x)vnth (vcons A E) fin0 = vnth (vcons A F) (match fin0 in fin n return n = S n0 -> fin (S m) with | @fin0 n => apply_noConfusion (S n) (S n0) (fun H : n = n0 => DepElim.solution_left n0 fin0 n H) | @finS n x => apply_noConfusion (S n) (S n0) (fun H : n = n0 => DepElim.solution_left n0 (fun x0 : fin n0 => finS (r x0)) n H x) end eq_refl)n1, m: nat
E: env n1
F: env m
A: type
r: fin n1 -> fin m
e: forall x : fin n1, vnth E x = vnth F (r x)
x: fin n1vnth (vcons A E) (finS x) = vnth (vcons A F) (match finS x in fin n return n = S n1 -> fin (S m) with | @fin0 n => apply_noConfusion (S n) (S n1) (fun H : n = n1 => DepElim.solution_left n1 fin0 n H) | @finS n x0 => apply_noConfusion (S n) (S n1) (fun H : n = n1 => DepElim.solution_left n1 (fun x1 : fin n1 => finS (r x1)) n H x0) end eq_refl)n0, m: nat
E: env n0
F: env m
A: type
r: fin n0 -> fin m
e: forall x : fin n0, vnth E x = vnth F (r x)vnth (vcons A E) fin0 = vnth (vcons A F) (match fin0 in fin n return n = S n0 -> fin (S m) with | @fin0 n => apply_noConfusion (S n) (S n0) (fun H : n = n0 => DepElim.solution_left n0 fin0 n H) | @finS n x => apply_noConfusion (S n) (S n0) (fun H : n = n0 => DepElim.solution_left n0 (fun x0 : fin n0 => finS (r x0)) n H x) end eq_refl)n0, m: nat
E: env n0
F: env m
A: type
r: fin n0 -> fin m
e: forall x : fin n0, vnth E x = vnth F (r x)vnth (vcons A E) fin0 = vnth (vcons A F) fin0reflexivity.n0, m: nat
E: env n0
F: env m
A: type
r: fin n0 -> fin m
e: forall x : fin n0, vnth E x = vnth F (r x)A = An1, m: nat
E: env n1
F: env m
A: type
r: fin n1 -> fin m
e: forall x : fin n1, vnth E x = vnth F (r x)
x: fin n1vnth (vcons A E) (finS x) = vnth (vcons A F) (match finS x in fin n return n = S n1 -> fin (S m) with | @fin0 n => apply_noConfusion (S n) (S n1) (fun H : n = n1 => DepElim.solution_left n1 fin0 n H) | @finS n x0 => apply_noConfusion (S n) (S n1) (fun H : n = n1 => DepElim.solution_left n1 (fun x1 : fin n1 => finS (r x1)) n H x0) end eq_refl)simp vnth.n1, m: nat
E: env n1
F: env m
A: type
r: fin n1 -> fin m
e: forall x : fin n1, vnth E x = vnth F (r x)
x: fin n1vnth (vcons A E) (finS x) = vnth (vcons A F) (finS (r x))n, m, k: nat
E: env n
F: env m
G: env k
r: fin n -> fin m
h: forall x : fin n, vnth E x = vnth F (r x)
r': fin m -> fin k
h': forall x : fin m, vnth F x = vnth G (r' x)
x: fin nvnth E x = vnth G (r' (r x))n, m, k: nat
E: env n
F: env m
G: env k
r: fin n -> fin m
h: forall x : fin n, vnth E x = vnth F (r x)
r': fin m -> fin k
h': forall x : fin m, vnth F x = vnth G (r' x)
x: fin nvnth E x = vnth G (r' (r x))reflexivity.n, m, k: nat
E: env n
F: env m
G: env k
r: fin n -> fin m
h: forall x : fin n, vnth E x = vnth F (r x)
r': fin m -> fin k
h': forall x : fin m, vnth F x = vnth G (r' x)
x: fin nvnth G (r' (r x)) = vnth G (r' (r x))
Semantic valuation:
Definition sval {n m} (E : env n) (F : env m) := forall x, sem F (vnth E x).Definition tid A : term vnil (A ~> A) := tlam A (tvar (E := vcons _ vnil) fin0).
Test on those: