source: src/ASM/BitVectorTrie.ma @ 1074

Last change on this file since 1074 was 1074, checked in by boender, 8 years ago
  • added lookup lemma
File size: 18.8 KB
Line 
1include "basics/types.ma".
2
3include "utilities/option.ma".
4include "ASM/BitVector.ma".
5
6inductive BitVectorTrie (A: Type[0]): nat → Type[0] ≝
7  Leaf: A → BitVectorTrie A O
8| Node: ∀n: nat. BitVectorTrie A n → BitVectorTrie A n → BitVectorTrie A (S n)
9| Stub: ∀n: nat. BitVectorTrie A n.
10
11let rec fold (A, B: Type[0]) (n: nat) (f: BitVector n → A → B → B)
12 (t: BitVectorTrie A n) (b: B) on t: B ≝
13 (match t return λx.λ_.x = n → B with
14  [ Leaf l ⇒ λ_.f (zero ?) l b
15  | Node h l r ⇒ λK.
16    fold A B h (λx.f ((VCons ? h false x)⌈(S h) ↦ n⌉)) l
17      (fold A B h (λx.f ((VCons ? h true x)⌈(S h) ↦ n⌉)) r b)
18  | Stub _ ⇒ λ_.b
19  ]) (refl ? n).
20 @K
21qed.
22
23(* these two can probably be generalized w/r/t the second type and
24 * some sort of equality relationship *)
25lemma fold_eq:
26  ∀A: Type[0].
27  ∀n: nat.
28  ∀f.
29  ∀t.
30  ∀P, Q: Prop.
31  (P → Q) → (∀a,t',P,Q.(P → Q) → f a t' P → f a t' Q) → fold A ? n f t P → fold A ? n f t Q.
32 #A #n #f #t #P #Q #H
33 generalize in match (refl ? n) generalize in match H -H; generalize in match Q -Q; generalize in match P -P;
34 elim t in f ⊢ (? → ? → ? → ???% → ? → ???%%%? → ???%%%?)
35 [ #a #f #P #Q #HPQ #_ #Hf #HP whd in HP; whd @(Hf (zero 0) a P Q HPQ HP)
36 | #h #l #r #Hl #Hr #f #P #Q #HPQ #_ #Hf #HP normalize normalize in HP; @(Hl ? (fold A Prop h (λx.f (true:::x)) r P) (fold A Prop h (λx.f (true:::x)) r Q) ? (refl ? h) ?)
37   [ @(Hr ? P Q HPQ (refl ? h) ?)
38     #a #t' #X #Y #HXY #Hff @(Hf (true:::a) t' X Y HXY Hff)
39   | #a #t' #X #Y #HXY #Hff @(Hf (false:::a) t' X Y HXY Hff) ]
40 | #h #f #P #Q #HPQ #_ #Hf #HP whd in HP; whd @(HPQ HP) ]
41  @HP
42qed.
43 
44lemma fold_init:
45  ∀A:Type[0].
46  ∀n:nat.
47  ∀f.
48  ∀t.
49  ∀P: Prop.
50  (∀a,t',P.f a t' P → P) → fold A Prop n f t P → P.
51 #A #n #f #t #P #H generalize in match (refl ? n) generalize in match H -H; generalize in match P -P;
52 elim t in f ⊢ (? → ? → ???% → ???%%%? → ?) -t
53 [ #a #f #P #Hf #_ normalize @(Hf [[]])
54 | #h #l #r #Hl #Hr #f #P #Hf #_ normalize #HP @(Hr (λx.f (true:::x)))
55   [ #a #t' #X @(Hf (true:::a) t' X) | @(refl ? h) | @(Hl (λx.f (false:::x)))
56     [ #a #t' #X @(Hf (false:::a) t' X) | @(refl ? h) | @HP ]
57   ]
58 | #h #f #P #Hf #_ normalize //
59 ]
60qed.
61 
62definition forall
63 ≝
64  λA.λn.λt:BitVectorTrie A n.λP.fold ? ? ? (λk.λa.λacc.(P k a) ∧ acc) t True.
65 
66lemma forall_nodel:
67  ∀A:Type[0].
68  ∀n:nat.
69  ∀l,r.
70  ∀P:BitVector (S n) → A → Prop.
71  forall A (S n) (Node ? n l r) P → forall A n l (λx.λa.P (false:::x) a).
72 #A #n #l #r #P #Hl
73 whd @(fold_eq A n ? ? (fold A ? n (λk.λa.λacc.P (true:::k) a∧acc) r True) True)
74 [ //
75 | #n #t' #X #Y #HXY #HX %1
76   [ @(proj1 ? ? HX) | @HXY @(proj2 ? ? HX) ]
77 | whd in Hl @Hl ]
78qed.
79 
80lemma forall_noder:
81  ∀A:Type[0].
82  ∀n:nat.
83  ∀l,r.
84  ∀P:BitVector (S n) → A → Prop.
85  forall A (S n) (Node ? n l r) P → forall A n r (λx.λa.P (true:::x) a).
86 #A #n #l #r #P #Hr
87 whd @(fold_init A n (λk.λa.λacc.P (false:::k) a∧acc) l) 
88 [ #n #t' #P #HP @(proj2 ? ? HP)
89 | @Hr
90 ]
91qed.
92
93lemma forall_node:
94  ∀A.∀n.∀l,r.∀P:BitVector (S n) → A → Prop.
95  forall A n l (λx.λa.P (false:::x) a) → forall A n r (λx.λa.P (true:::x) a) →
96  forall A (S n) (Node ? n l r) P.
97 #A #n #l #r #P #Hl #Hr
98 normalize @(fold_eq … True)
99 [ #_ @Hr
100 | #x #t' #X #Y #HXY #HP %1 [ @(proj1 … HP) | @HXY @(proj2 … HP) ]
101 | @Hl
102 ]
103qed.
104
105let rec lookup_opt (A: Type[0]) (n: nat)
106                (b: BitVector n) (t: BitVectorTrie A n) on t
107       : option A ≝
108 (match t return λx.λ_. BitVector x → option A with
109  [ Leaf l ⇒ λ_.Some ? l
110  | Node h l r ⇒ λb. lookup_opt A ? (tail … b) (if head' … b then r else l)
111  | Stub _ ⇒ λ_.None ?
112  ]) b.
113
114definition member ≝
115  λA.
116  λn.
117  λb: BitVector n.
118  λt: BitVectorTrie A n.
119  match lookup_opt A n b t with
120  [ None ⇒ false
121  | _    ⇒ true
122  ].
123
124definition member_p ≝
125  λA.
126  λn.
127  λb: BitVector n.
128  λt: BitVectorTrie A n.
129  match lookup_opt A n b t with
130  [ None ⇒ False
131  | _    ⇒ True
132  ].
133 
134lemma forall_lookup:
135 ∀A.
136  ∀n.
137  ∀t:BitVectorTrie A n.
138  ∀P:BitVector n → A → Prop.
139  forall A n t P → ∀a:A.∀b.lookup_opt A n b t = Some ? a → P b a.
140 #A #n #t #P generalize in match (refl ? n) elim t in P ⊢ (???% → ??%%? → ? → ? → ??(??%%%)? → ?)
141 [ #x #f #_ #Hf #a #b whd in Hf; #Hb normalize in Hb; destruct >(BitVector_O b) @(proj1 ? ? Hf)
142 | #h #l #r #Hl #Hr #f #_ #Hf #a #b #Hb cases (BitVector_Sn h b)
143   #hd #bla elim bla -bla #tl #Htl >Htl in Hb; #Hb cases hd in Hb;
144   [ #Hb normalize in Hb; @(Hr (λx.λa.f (true:::x) a) (refl ? h))
145     [ @(forall_noder A h l r f Hf)
146     | @Hb
147     ]
148   | #Hb normalize in Hb; @(Hl (λx.λa.f (false:::x) a) (refl ? h))
149     [ @(forall_nodel A h l r f Hf)
150     | @Hb
151     ]
152   ]
153 | #n #f #_ #Hf #a #b #Hb normalize in Hb; destruct
154qed.
155
156lemma lookup_forall:
157 ∀A:Type[0].∀n.∀t:BitVectorTrie A n.∀P:BitVector n → A → Prop. 
158 (∀a:A.∀b:BitVector n.lookup_opt A n b t = Some ? a → P b a) → forall A n t P.
159 #A #n #t elim t
160 [ #x #P #HP normalize %1 [ @HP normalize @refl | // ]
161 | #h #l #r #Hl #Hr #P #HP @forall_node
162   [ @Hl #a #b #Hlookup @HP normalize @Hlookup
163   | @Hr #a #b #Hlookup @HP normalize @Hlookup
164   ]
165 | #n #P #HP normalize //
166 ]   
167qed.
168 
169let rec lookup (A: Type[0]) (n: nat)
170                (b: BitVector n) (t: BitVectorTrie A n) (a: A) on b
171       : A ≝
172  (match b return λx.λ_. x = n → A with
173    [ VEmpty ⇒
174      (match t return λx.λ_. O = x → A with
175        [ Leaf l ⇒ λ_.l
176        | Node h l r ⇒ λK.⊥
177        | Stub s ⇒ λ_.a
178        ])
179    | VCons o hd tl ⇒
180      match t return λx.λ_. (S o) = x → A with
181        [ Leaf l ⇒ λK.⊥
182        | Node h l r ⇒
183           match hd with
184             [ true ⇒ λK. lookup A h (tl⌈o ↦ h⌉) r a
185             | false ⇒ λK. lookup A h (tl⌈o ↦ h⌉) l a
186             ]
187        | Stub s ⇒ λ_. a]
188    ]) (refl ? n).
189  [1,2:
190    destruct
191  |*:
192    @ injective_S
193    //
194  ]
195qed.
196
197let rec prepare_trie_for_insertion (A: Type[0]) (n: nat) (b: BitVector n) (a:A) on b : BitVectorTrie A n ≝
198   match b with
199    [ VEmpty ⇒ Leaf A a
200    | VCons o hd tl ⇒
201      match hd with
202        [ true ⇒  Node A o (Stub A o) (prepare_trie_for_insertion A o tl a)
203        | false ⇒ Node A o (prepare_trie_for_insertion A o tl a) (Stub A o)
204        ]
205    ].
206
207let rec insert (A: Type[0]) (n: nat) (b: BitVector n) (a: A) on b: BitVectorTrie A n → BitVectorTrie A n ≝
208  (match b with
209    [ VEmpty ⇒ λ_. Leaf A a
210    | VCons o hd tl ⇒ λt.
211          match t return λy.λ_. S o = y → BitVectorTrie A (S o) with
212            [ Leaf l ⇒ λprf.⊥
213            | Node p l r ⇒ λprf.
214               match hd with
215                [ true ⇒  Node A o (l⌈p ↦ o⌉) (insert A o tl a (r⌈p ↦ o⌉))
216                | false ⇒ Node A o (insert A o tl a (l⌈p ↦ o⌉)) (r⌈p ↦ o⌉)
217                ]
218            | Stub p ⇒ λprf. (prepare_trie_for_insertion A ? (hd:::tl) a)
219            ] (refl ? (S o))
220    ]).
221  [ destruct
222  |*:
223    @ injective_S
224    //
225  ]
226qed.
227 
228let rec update (A: Type[0]) (n: nat) (b: BitVector n) (a: A) on b: BitVectorTrie A n → option (BitVectorTrie A n) ≝
229  (match b with
230    [ VEmpty ⇒ λt. match t return λy.λ_. O = y → option (BitVectorTrie A O) with
231                   [ Leaf _ ⇒ λ_. Some ? (Leaf A a)
232                   | Stub _ ⇒ λ_. None ?
233                   | Node _ _ _ ⇒ λprf. ⊥
234                   ] (refl ? O)
235    | VCons o hd tl ⇒ λt.
236          match t return λy.λ_. S o = y → option (BitVectorTrie A (S o)) with
237            [ Leaf l ⇒ λprf.⊥
238            | Node p l r ⇒ λprf.
239               match hd with
240                [ true ⇒  option_map ?? (λv. Node A o (l⌈p ↦ o⌉) v) (update A o tl a (r⌈p ↦ o⌉))
241                | false ⇒ option_map ?? (λv. Node A o v (r⌈p ↦ o⌉)) (update A o tl a (l⌈p ↦ o⌉))
242                ]
243            | Stub p ⇒ λprf. None ?
244            ] (refl ? (S o))
245    ]).
246  [ 1,2: destruct
247  |*:
248    @ injective_S @sym_eq @prf
249  ]
250qed.
251
252let rec merge (A: Type[0]) (n: nat) (b: BitVectorTrie A n) on b: BitVectorTrie A n → BitVectorTrie A n ≝
253  match b return λx. λ_. BitVectorTrie A x → BitVectorTrie A x with
254  [ Stub _ ⇒ λc. c
255  | Leaf l ⇒ λc. match c with [ Leaf a ⇒ Leaf ? a | _ ⇒ Leaf ? l ]
256  | Node p l r ⇒
257    λc.
258    (match c return λx. λ_. x = (S p) → BitVectorTrie A (S p) with
259    [ Node p' l' r' ⇒ λprf. Node ? ? (merge ?? l (l'⌈p' ↦ p⌉)) (merge ?? r (r'⌈p' ↦ p⌉))
260    | Stub _ ⇒ λprf. Node ? p l r
261    | Leaf _ ⇒ λabsd. ?
262    ] (refl ? (S p)))
263  ].
264  [1:
265      destruct(absd)
266  |2,3:
267      @ injective_S
268        assumption
269  ]
270qed.
271
272lemma BitVectorTrie_O:
273 ∀A:Type[0].∀v:BitVectorTrie A 0.(∃w. v ≃ Leaf A w) ∨ v ≃ Stub A 0.
274 #A #v generalize in match (refl … O) cases v in ⊢ (??%? → (?(??(λ_.?%%??)))(?%%??))
275  [ #w #_ %1 %[@w] %
276  | #n #l #r #abs @⊥ destruct(abs)
277  | #n #EQ %2 >EQ %]
278qed.
279
280lemma BitVectorTrie_Sn:
281 ∀A:Type[0].∀n.∀v:BitVectorTrie A (S n).(∃l,r. v ≃ Node A n l r) ∨ v ≃ Stub A (S n).
282 #A #n #v generalize in match (refl … (S n)) cases v in ⊢ (??%? → (?(??(λ_.??(λ_.?%%??))))%)
283  [ #m #abs @⊥ destruct(abs)
284  | #m #l #r #EQ %1 <(injective_S … EQ) %[@l] %[@r] //
285  | #m #EQ %2 // ]
286qed.
287
288lemma lookup_prepare_trie_for_insertion_hit:
289 ∀A:Type[0].∀a,v:A.∀n.∀b:BitVector n.
290  lookup … b (prepare_trie_for_insertion … b v) a = v.
291 #A #a #v #n #b elim b // #m #hd #tl #IH cases hd normalize //
292qed.
293 
294lemma lookup_insert_hit:
295 ∀A:Type[0].∀a,v:A.∀n.∀b:BitVector n.∀t:BitVectorTrie A n.
296  lookup … b (insert … b v t) a = v.
297 #A #a #v #n #b elim b -b -n //
298 #n #hd #tl #IH #t cases(BitVectorTrie_Sn … t)
299  [ * #l * #r #JMEQ >JMEQ cases hd normalize //
300  | #JMEQ >JMEQ cases hd normalize @lookup_prepare_trie_for_insertion_hit ]
301qed.
302
303lemma lookup_prepare_trie_for_insertion_miss:
304 ∀A:Type[0].∀a,v:A.∀n.∀c,b:BitVector n.
305  (notb (eq_bv ? b c)) → lookup … b (prepare_trie_for_insertion … c v) a = a.
306 #A #a #v #n #c elim c
307  [ #b >(BitVector_O … b) normalize #abs @⊥ //
308  | #m #hd #tl #IH #b cases(BitVector_Sn … b) #hd' * #tl' #JMEQ >JMEQ
309    cases hd cases hd' normalize
310    [2,3: #_ cases tl' //
311    |*: change with (bool_to_Prop (notb (eq_bv ???)) → ?) /2/ ]]
312qed.
313 
314lemma lookup_insert_miss:
315 ∀A:Type[0].∀a,v:A.∀n.∀c,b:BitVector n.∀t:BitVectorTrie A n.
316  (notb (eq_bv ? b c)) → lookup … b (insert … c v t) a = lookup … b t a.
317 #A #a #v #n #c elim c -c -n
318  [ #b #t #DIFF @⊥ whd in DIFF; >(BitVector_O … b) in DIFF //
319  | #n #hd #tl #IH #b cases(BitVector_Sn … b) #hd' * #tl' #JMEQ >JMEQ
320    #t cases(BitVectorTrie_Sn … t)
321    [ * #l * #r #JMEQ >JMEQ cases hd cases hd' #H normalize in H;
322     [1,4: change in H with (bool_to_Prop (notb (eq_bv ???))) ] normalize // @IH //
323    | #JMEQ >JMEQ cases hd cases hd' #H normalize in H;
324     [1,4: change in H with (bool_to_Prop (notb (eq_bv ???))) ] normalize
325     [3,4: cases tl' // | *: @lookup_prepare_trie_for_insertion_miss //]]]
326qed.
327
328lemma lookup_stub:
329 ∀A.∀n.∀b.∀a.
330 lookup A n b (Stub A ?) a = a.
331 #A #n #b #a cases n in b ⊢ (??(??%%%?)?)
332 [ #b >(BitVector_O b) normalize @refl
333 | #h #b cases (BitVector_Sn h b) #hd #X elim X -X; #tl #Hb >Hb cases hd
334   [ normalize @refl
335   | normalize @refl
336   ]
337 ]   
338qed.   
339
340lemma lookup_opt_lookup:
341  ∀A:Type[0].∀n:nat.∀b:BitVector n.∀t:BitVectorTrie A n.∀a:A.
342  lookup_opt A n b t = Some A a → ∀x.lookup A n b t x = a.
343 #A #n #b #t #a generalize in match (refl ? n) elim t in b ⊢ (???% → ??(??%%%)? → ? → ?)
344 [ #a #B #_ #H #x normalize in H; >(BitVector_O B) normalize destruct @refl
345 | #h #l #r #Hl #Hr #b #_ #H #x cases (BitVector_Sn h b) #hd #X elim X; -X; #tl #Hb
346   >Hb >Hb in H; cases hd
347   [ normalize #Hlookup @(Hr ? (refl ? h)) @Hlookup
348   | normalize #Hlookup @(Hl ? (refl ? h)) @Hlookup
349   ]
350 | #n #B #_ #H #x normalize in H; destruct
351 ]
352qed.
353
354lemma lookup_lookup_opt:
355  ∀A.∀n.∀b.∀t.∀x,a.
356  lookup A n b t x = a → x ≠ a → lookup_opt A n b t = Some A a.
357 #A #n #b #t #x #a generalize in match (refl ? n) elim t in b ⊢ (???% → ? → ?)
358 [ #z #B #_ #H #Hx >(BitVector_O B) in H; normalize #H >H @refl
359 | #h #l #r #Hl #Hr #B #_ #H #Hx cases (BitVector_Sn h B) #hd #X elim X; -X #tl #HB
360   >HB >HB in H; cases hd
361   [ normalize #H >(Hr tl (refl ? h) H Hx) @refl
362   | normalize #H >(Hl tl (refl ? h) H Hx) @refl
363   ]
364 | #n #B #_ #H #Hx cases B in H;
365   [ normalize #Hx' | #n' #b #v normalize #Hx' ]
366   @⊥ @(absurd (eq ? x a)) [1,3: @Hx' |2,4: @Hx ]
367 ]
368qed.
369
370 
371 
372lemma lookup_opt_prepare_trie_for_insertion_hit:
373 ∀A:Type[0].∀v:A.∀n.∀b:BitVector n.
374  lookup_opt … b (prepare_trie_for_insertion … b v) = Some A v.
375 #A #v #n #b elim b // #m #hd #tl #IH cases hd normalize //
376qed.
377
378lemma lookup_opt_prepare_trie_for_insertion_miss:
379 ∀A:Type[0].∀v:A.∀n.∀c,b:BitVector n.
380  (notb (eq_bv ? b c)) → lookup_opt … b (prepare_trie_for_insertion … c v) = None ?.
381 #A #v #n #c elim c
382  [ #b >(BitVector_O … b) normalize #abs @⊥ //
383  | #m #hd #tl #IH #b cases(BitVector_Sn … b) #hd' * #tl' #JMEQ >JMEQ
384    cases hd cases hd' normalize
385    [2,3: #_ cases tl' //
386    |*: change with (bool_to_Prop (notb (eq_bv ???)) → ?) @IH ]]
387qed.
388
389lemma lookup_opt_insert_hit:
390 ∀A:Type[0].∀v:A.∀n.∀b:BitVector n.∀t:BitVectorTrie A n.
391  lookup_opt … b (insert … b v t) = Some A v.
392 #A #v #n #b #t elim t in b ⊢ (??(??%%%)?)
393 [ #x #b >(BitVector_O b) normalize @refl
394 | #h #l #r #Hl #Hr #b cases (BitVector_Sn h b) #hd #X elim X -X; #tl #Hb >Hb cases hd
395   [ normalize @Hr
396   | normalize @Hl
397   ]
398 | #n' #b cases n' in b ⊢ ?
399   [ #b >(BitVector_O b) normalize @refl
400   | #m #b cases (BitVector_Sn m b) #hd #X elim X -X; #tl #Hb >Hb cases hd
401     normalize @lookup_opt_prepare_trie_for_insertion_hit
402   ]
403 ]
404qed.
405
406lemma lookup_opt_insert_miss:
407 ∀A:Type[0].∀v:A.∀n.∀c,b:BitVector n.∀t:BitVectorTrie A n.
408  (notb (eq_bv ? b c)) → lookup_opt … b (insert … c v t) = lookup_opt … b t.
409 #A #v #n #c elim c -c -n
410  [ #b #t #DIFF @⊥ whd in DIFF; >(BitVector_O … b) in DIFF //
411  | #n #hd #tl #IH #b cases(BitVector_Sn … b) #hd' * #tl' #JMEQ >JMEQ
412    #t cases(BitVectorTrie_Sn … t)
413    [ * #l * #r #JMEQ >JMEQ cases hd cases hd' #H normalize in H;
414     [1,4: change in H with (bool_to_Prop (notb (eq_bv ???))) ] normalize // @IH //
415    | #JMEQ >JMEQ cases hd cases hd' #H normalize in H;
416     [1,4: change in H with (bool_to_Prop (notb (eq_bv ???))) ] normalize
417     [3,4: cases tl' // | *: @lookup_opt_prepare_trie_for_insertion_miss //]]]
418qed.
419
420lemma forall_insert_inv1:
421  ∀A.∀n.∀b.∀a.∀t.∀P.
422  forall A n (insert A n b a t) P → P b a.
423 #A #n #b #a #t #P #H @(forall_lookup ? ? (insert A n b a t))
424 [ @H
425 | >(lookup_opt_insert_hit A ? n b) @(refl ? (Some A a))
426 ]
427qed.
428
429lemma forall_insert_inv2a:
430  ∀A:Type[0].∀n:nat.∀b.∀a.∀t.∀P.
431  lookup_opt A n b t = (None A)  → forall A n (insert A n b a t) P → forall A n t P.
432 #A #n #b #a #t generalize in match (refl ? n) elim t in b ⊢ (???% → ? → ??(??%%%)? → ??%%% → ??%%%)
433 [ #x #b #_ #P >(BitVector_O b) normalize #H destruct
434 | #h #l #r #Hl #Hr #b #_ #P cases (BitVector_Sn h b) #hd #X elim X -X; #tl #Hb >Hb cases hd #Hlookup #H
435   [ normalize in H; normalize
436     @(fold_eq … (fold A ? ? (λx.λa0.λacc.P (true:::x) a0∧acc) (insert … tl a r) True) … H)
437     [ #Hfold @(Hr tl (refl ? h) ? Hlookup Hfold)
438     | #x #t' #X #Y #HXY #HP %1 [ @(proj1 ? ? HP) | @(HXY (proj2 ? ?HP)) ]
439     ]
440   | normalize in H; normalize     
441     @(fold_eq … True)
442     [ #_ @(fold_init A h (λx.λa0.λacc.P (false:::x) a0 ∧ acc) (insert A h tl a l))
443       [ #z #t' #X #HX @(proj2 ? ? HX)
444       | @H ]
445     | #z #t' #X #Y #HXY #HP %1 [ @(proj1 ? ? HP) | @(HXY (proj2 ? ? HP)) ]
446     | @(Hl tl (refl ? h) ? Hlookup) normalize
447       @(fold_eq … (fold A ? ? (λx.λa0.λacc.P (true:::x) a0∧acc) r True))
448       [ //
449       | #z #t' #X #Y #HXY #HP %1 [ @(proj1 ? ? HP) | @(HXY (proj2 ? ? HP)) ]
450       | @H
451       ]
452     ]
453   ]
454 | #n #b #_ #P #Hlookup #Hf normalize // ]
455qed. 
456
457lemma forall_insert_inv2b:
458  ∀A:Type[0].∀n:nat.∀b:BitVector n.∀a:A.∀t.∀P:(BitVector n → A → Prop).
459  (∀x.(lookup_opt A n b t = Some A x) → P b x) → forall A n (insert A n b a t) P → forall A n t P.
460 #A #n #b #a #t generalize in match (refl ? n) elim t in b ⊢ (???% → % → ? → ??%%% → ?)
461 [ #x #b #_ #P >(BitVector_O b) normalize #HP #Hf %1 [ @HP @refl | @(proj2 ? ? Hf) ]
462 | #h #l #r #Hl #Hr #b #_ cases (BitVector_Sn h b) #hd #X elim X -X; #tl #Hb >Hb cases hd #P #HP #Hf
463   [ normalize in Hf; normalize
464     @(fold_eq … (fold A ? ? (λx.λa0.λacc.P (true:::x) a0∧acc) (insert … tl a r) True) … Hf)
465     [ #Hfold @(Hr tl (refl ? h) ? HP Hfold)
466     | #x #t' #X #Y #HXY #HP %1 [ @(proj1 ? ? HP) | @(HXY (proj2 ? ? HP)) ]
467     ]
468   | normalize in H; normalize     
469     @(fold_eq … True)
470     [ #_ @(fold_init A h (λx.λa0.λacc.P (false:::x) a0 ∧ acc) (insert A h tl a l))
471       [ #z #t' #X #HX @(proj2 ? ? HX)
472       | @Hf ]
473     | #z #t' #X #Y #HXY #HP %1 [ @(proj1 ? ? HP) | @(HXY (proj2 ? ? HP)) ]
474     | @(Hl tl (refl ? h) ? HP) normalize
475       @(fold_eq … (fold A ? ? (λx.λa0.λacc.P (true:::x) a0∧acc) r True))
476       [ //
477       | #z #t' #X #Y #HXY #HP %1 [ @(proj1 ? ? HP) | @(HXY (proj2 ? ? HP)) ]
478       | @Hf
479       ]
480     ]
481   ]
482 | #n #b #_ #P #Hlookup #Hf normalize // ]
483qed.
484
485lemma forall_prepare_tree_for_insertion:
486 ∀A:Type[0].∀h:nat.∀b:BitVector h.∀a:A.∀P.
487 P b a →
488 forall A h (prepare_trie_for_insertion A h b a) P.
489 #A #h #b elim b
490 [ #a #P #HP normalize %1 [ @HP | // ]
491 | #h #x #tl #Ha #a #P cases x #HP normalize @Ha @HP
492 ]
493qed.
494
495lemma forall_insert:
496  ∀A:Type[0].∀n:nat.∀b:BitVector n.∀a:A.∀t.∀P.
497  forall A n t P → P b a → forall A n (insert A n b a t) P.
498 #A #n #b #a #t generalize in match (refl ? n) elim t in b ⊢ (???% → % → ??%%% → %%? → ??%%%)
499 [ #x #b #_ #P >(BitVector_O b) normalize #H1 #H2 /2/
500 | #h #l #r #Hl #Hr #b #_ cases (BitVector_Sn h b) #hd #X elim X -X; #tl #Hb >Hb cases hd #P #Hf #HP
501   [ normalize in Hf; normalize
502     @(fold_eq A … (fold A … (λx.λa0.λacc.P (true:::x) a0∧acc) r True) … Hf)
503     [ #Hp @(Hr tl (refl ? h) ? Hp HP)
504     | #z #t' #X #Y #HXY #HP %1 [ @(proj1 ? ? HP) | @(HXY (proj2 ? ? HP)) ]
505     ]
506   | normalize in Hf; normalize
507     @(fold_eq … True)
508     [ #_ @(fold_init A h (λx.λa0.λacc.P (false:::x) a0∧acc) l)
509       [ #z #t' #X #HX @(proj2 ? ? HX)
510       | @Hf ]
511     | #z #t' #X #Y #HXY #HP %1 [ @(proj1 ? ? HP) | @(HXY (proj2 ? ? HP)) ]
512     | @(Hl tl (refl ? h) ? ? HP)
513       normalize @(fold_eq … (fold A ? ? (λx.λa0.λacc.P (true:::x) a0∧acc) r True))
514       [ //
515       | #z #t' #X #Y #HXY #HP %1 [ @(proj1 ? ? HP) | @(HXY (proj2 ? ? HP)) ]
516       | @Hf
517       ]
518     ]
519   ]
520 | #n #b #_ elim b in t ⊢ (% → ? → ? → ??%%%)
521   [ #b #P #Hf #HP normalize %1 [ @HP | // ]
522   | #h #hd #tl #H #b #P #Hf cases hd #HP normalize @(forall_prepare_tree_for_insertion A h tl a ? HP)
523   ]
524 ]
525qed.   
Note: See TracBrowser for help on using the repository browser.