-definition iota : nat → nat → list nat ≝
- λn,m. nat_rect (λ_.list ?) (nil ?) (λx,acc.cons ? (n+x) acc) m.
-
-let rec map (A,B:Type) (f: A → B) (l : list A) on l : list B ≝
- match l with [ nil ⇒ nil ? | cons x tl ⇒ f x :: (map A B f tl)].
-
-(* ### induction principle for functions visiting 2 lists in parallel *)
-lemma list_ind2 :
- ∀T1,T2:Type.∀l1:list T1.∀l2:list T2.∀P:list T1 → list T2 → Prop.
- length ? l1 = length ? l2 →
- (P (nil ?) (nil ?)) →
- (∀tl1,tl2,hd1,hd2. P tl1 tl2 → P (hd1::tl1) (hd2::tl2)) →
- P l1 l2.
-intros (T1 T2 l1 l2 P Hl Pnil Pcons);
-generalize in match Hl; clear Hl; generalize in match l2; clear l2;
-elim l1 1 (l2 x1); [ cases l2; intros (Hl); [assumption| destruct Hl]]
-intros 3 (tl1 IH l2); cases l2; [1: simplify; intros 1 (Hl); destruct Hl]
-intros 1 (Hl); apply Pcons; apply IH; destruct Hl; assumption;
-qed.
-
-lemma eq_map : ∀A,B,f,g,l. (∀x.f x = g x) → map A B f l = map A B g l.
-intros (A B f g l Efg); elim l; simplify; [1: reflexivity ];
-rewrite > (Efg t); rewrite > H; reflexivity;
-qed.
-