archive-nl.com » NL » R » ROBBERTKREBBERS.NL

Total: 145

Choose link from "Titles, links and description words view":

Or switch to "Titles and links view".
  • Module fin_collections
    congruence Qed Lemma elem of or empty X x x X X Proof destruct elements X as x xs eqn E right apply equiv empty intros x Ex by rewrite elements spec E elem of nil in Ex left exists x rewrite elements spec E by constructor Qed Lemma choose X X x x X Proof destruct elem of or empty X as x by exists x done Qed Lemma size pos choose X 0 size X x x X Proof intros E1 apply choose intros E2 rewrite E2 size empty in E1 by apply Lt lt n 0 0 Qed Lemma size 1 choose X size X 1 x X x Proof intros E destruct size pos choose X rewrite E auto with arith exists x apply elem of equiv split intro rewrite elem of singleton eauto using size singleton inv solve elem of Qed Lemma size union X Y X Y size X Y size X size Y Proof intros E unfold size collection size simpl rewrite app length apply Permutation length NoDup Permutation apply elements nodup apply NoDup app repeat split try apply elements nodup intros x rewrite elements spec esolve elem of intros rewrite elem of app elements spec solve elem of Qed Instance elem of dec slow x A X C Decision x X 100 Proof refine cast if decide rel x elements X by rewrite elements spec Defined Global Program Instance collection subseteq dec slow X Y C Decision X Y 100 match decide rel size X Y 0 with left E1 left right E1 right end Next Obligation intros x Ex apply dec stable intro destruct proj1 elem of empty x apply size empty inv E1 by rewrite elem of difference Qed Next Obligation intros E2 destruct E1 apply size empty iff equiv empty intros x rewrite elem of difference intros E3 by apply E2 in E3 Qed Lemma size union alt X Y size X Y size X size Y X Proof rewrite size union by solve elem of setoid replace Y X with Y X X by esolve elem of rewrite union difference commutative solve elem of Qed Lemma subseteq size X Y X Y size X size Y Proof intros rewrite union difference X Y size union alt by done lia Qed Lemma subset size X Y X Y size X size Y Proof intros rewrite union difference X Y by solve elem of rewrite size union alt difference twice cut size Y X 0 lia by apply size non empty iff non empty difference Qed Lemma collection wf wf subset C Proof apply well founded lt compat with size subset size Qed Lemma collection ind P C Prop Proper iff P P x X x X P X P x X X P X Proof intros Hemp Hadd apply well founded induction with apply collection wf intros X IH destruct elem of or empty X as x HX rewrite union difference x X by solve elem of apply Hadd

    Original URL path: http://robbertkrebbers.nl/research/ch2o/fossacs2013/fin_collections.html (2015-08-10)
    Open archived version from archive


  • Module listset
    Proof split by apply not elem of nil by apply elem of list singleton intros apply elem of app Qed Context x y A Decision x y Instance listset intersection Intersection listset A λ l k match l k with Listset l Listset k Listset list intersection l k end Instance listset difference Difference listset A λ l k match l k with Listset l Listset k Listset list difference l k end Instance listset intersection with IntersectionWith A listset A λ f l k match l k with Listset l Listset k Listset list intersection with f l k end Instance listset filter Filter A listset A λ P l match l with Listset l Listset filter P l end Global Instance Collection A listset A Proof split apply intros apply elem of list intersection intros apply elem of list difference intros apply elem of list intersection with Qed Instance listset elems Elements A listset A remove dups listset car Global Instance FinCollection A listset A Proof split apply intros apply elem of list filter symmetry apply elem of remove dups intros apply remove dups nodup Qed End listset These instances are declared using Hint Extern to avoid too eager type class search Hint Extern 1 ElemOf listset eapply listset elem of typeclass instances Hint Extern 1 Empty listset eapply listset empty typeclass instances Hint Extern 1 Singleton listset eapply listset singleton typeclass instances Hint Extern 1 Union listset eapply listset union typeclass instances Hint Extern 1 Intersection listset eapply listset intersection typeclass instances Hint Extern 1 IntersectionWith listset eapply listset intersection with typeclass instances Hint Extern 1 Difference listset eapply listset difference typeclass instances Hint Extern 1 Elements listset eapply listset elems typeclass instances Hint Extern 1 Filter listset eapply listset filter typeclass instances Instance listset ret MRet

    Original URL path: http://robbertkrebbers.nl/research/ch2o/fossacs2013/listset.html (2015-08-10)
    Open archived version from archive

  • Module fresh_numbers
    apply collection fold proper solve proper intros rewrite N max assoc f equal apply N max comm Qed Lemma Nmax max FinCollection N C X x x X x Nmax X N Proof apply collection fold ind λ b X x X x b N solve proper solve elem of solve elem of eauto using N le max l N le max r N le trans Qed Instance Nfresh FinCollection

    Original URL path: http://robbertkrebbers.nl/research/ch2o/fossacs2013/fresh_numbers.html (2015-08-10)
    Open archived version from archive

  • Module prelude
    Module prelude Require Export base tactics decidable orders option vector numbers ars collections fin collections listset fresh numbers list Generated by coq2html

    Original URL path: http://robbertkrebbers.nl/research/ch2o/fossacs2013/prelude.html (2015-08-10)
    Open archived version from archive

  • Module listset_nodup
    λ x LS x NoDup singleton x Instance listset nodup difference Difference C λ l k LS list difference nodup listset nodup car k listset nodup prf l Definition listset nodup union raw l k list A list A list difference l k k Lemma elem of listset nodup union raw l k x x listset nodup union raw l k x l x k Proof unfold listset nodup union raw rewrite elem of app elem of list difference intuition case decide x k intuition Qed Lemma listset nodup union raw nodup l k NoDup l NoDup k NoDup listset nodup union raw l k Proof intros apply NoDup app repeat split by apply list difference nodup intro rewrite elem of list difference intuition done Qed Instance listset nodup union Union C λ l k LS listset nodup union raw nodup listset nodup prf l listset nodup prf k Instance listset nodup intersection Intersection C λ l k LS list intersection nodup listset nodup car k listset nodup prf l Instance listset nodup intersection with IntersectionWith A C λ f l k LS remove dups list intersection with f listset nodup car l listset nodup car k remove dups nodup Instance listset nodup filter Filter A C λ P l LS filter nodup P listset nodup prf l Global Instance Collection A C Proof split split by apply not elem of nil by apply elem of list singleton intros apply elem of listset nodup union raw intros apply elem of list intersection intros apply elem of list difference intros unfold intersection with listset nodup intersection with elem of listset nodup elem of simpl rewrite elem of remove dups by apply elem of list intersection with Qed Global Instance listset nodup elems Elements A C listset nodup car Global Instance FinCollection

    Original URL path: http://robbertkrebbers.nl/research/ch2o/fossacs2013/listset_nodup.html (2015-08-10)
    Open archived version from archive

  • Module fin_maps
    None Some rewrite lookup delete None intuition Qed Lemma not elem of dom delete C SimpleCollection K C m M A i i dom C delete i m Proof apply not elem of dom C lookup delete Qed Lemma subseteq dom C SimpleCollection K C m1 m2 M A m1 m2 dom C m1 dom C m2 Proof unfold subseteq finmap subseteq collection subseteq intros rewrite elem of dom C inversion 1 eauto Qed Lemma subset dom C SimpleCollection K C m1 m2 M A m1 m2 dom C m1 dom C m2 Proof intros Hss1 Hss2 split by apply subseteq dom intros Hdom destruct Hss2 intros i x Hi specialize Hdom i rewrite elem of dom C in Hdom feed inversion Hdom eauto by erewrite Hss1 i in Hi by eauto Qed Lemma finmap wf wf subset M A Proof apply wf projected dom listset K by apply subset dom by apply collection wf Qed Lemma partial alter subseteq m M A i f m i None m partial alter f i m Proof intros Hi j x Hj rewrite lookup partial alter ne congruence Qed Lemma partial alter subset m M A i f m i None is Some f m i m partial alter f i m Proof intros Hi Hfi split by apply partial alter subseteq inversion Hfi as x Hx intros Hm apply Some ne None x rewrite Hm i x done by rewrite lookup partial alter Qed Lemma insert subseteq m M A i x m i None m i x m Proof apply partial alter subseteq Qed Lemma insert subset m M A i x m i None m i x m Proof intro apply partial alter subset eauto Qed Lemma delete subseteq m M A i delete i m m Proof intros j x rewrite lookup delete Some tauto Qed Lemma delete subseteq compat m1 m2 M A i m1 m2 delete i m1 delete i m2 Proof intros j x rewrite lookup delete Some intuition eauto Qed Lemma delete subset alt m M A i x m i Some x delete i m m Proof split apply delete subseteq intros Hi apply None ne Some x by rewrite lookup delete m i Hi i x Qed Lemma delete subset m M A i is Some m i delete i m m Proof inversion 1 eauto using delete subset alt Qed Induction principles We use the induction principle on finite collections to prove the following induction principle on finite maps Lemma finmap ind alt C P M A Prop FinCollection K C P i x m i dom C m P m P i x m m P m Proof intros Hemp Hinsert m apply collection ind λ X m dom C m X P m with dom C m solve proper clear m intros m Hm rewrite finmap empty done intros rewrite not elem of dom C Hm by solve elem of clear m intros i X Hi IH m Hdom assert x m i Some x as x apply is Some alt elem of dom C rewrite Hdom clear Hdom by solve elem of rewrite insert delete m i x by done apply Hinsert by apply not elem of dom delete C apply IH apply elem of equiv intros rewrite elem of dom delete C esolve elem of done Qed We use the listset implementation to prove an induction principle that does not use the map s domain Lemma finmap ind P M A Prop P i x m m i None P m P i x m m P m Proof setoid rewrite not elem of dom listset apply finmap ind alt listset P Qed End finmap common The finite map tactic The tactic simplify map by tac simplifies finite map expressions occuring in the conclusion and hypotheses It uses tac to discharge generated inequalities Tactic Notation simpl map by tactic3 tac repeat match goal with H context rewrite lookup empty in H H context rewrite lookup insert in H H context rewrite lookup insert ne in H by tac H context delete rewrite lookup delete in H H context delete rewrite lookup delete ne in H by tac H context rewrite lookup singleton in H H context rewrite lookup singleton ne in H by tac context rewrite lookup empty context rewrite lookup insert context rewrite lookup insert ne by tac context delete rewrite lookup delete context delete rewrite lookup delete ne by tac context rewrite lookup singleton context rewrite lookup singleton ne by tac context lookup A A i m let x fresh in evar x A let x eval unfold x in x in clear x let E fresh in assert m i Some x as E by tac rewrite E clear E end Create HintDb simpl map Tactic Notation simpl map simpl map by eauto with simpl map Tactic Notation simplify map equality by tactic3 tac repeat match goal with progress simpl map by tac progress simplify equality H None rewrite lookup singleton None in H H Some rewrite lookup singleton Some in H destruct H H1 m1 i Some x H2 m2 i Some y let H3 fresh in feed pose proof lookup weaken inv m1 m2 i x y as H3 done by tac done clear H2 symmetry in H3 H1 m1 i Some x H2 m2 i None let H3 fresh in assert m1 m2 as H3 by tac apply H3 in H1 congruence end Tactic Notation simplify map equality simplify map equality by eauto with simpl map More theorems on finite maps Section finmap more Context FinMap K M A Type Properties of conversion to lists Lemma finmap to list unique m M A i x y i x finmap to list m i y finmap to list m x y Proof rewrite elem of finmap to list congruence Qed Lemma finmap to list key nodup m M A NoDup fst finmap to list m Proof eauto using NoDup fmap fst finmap to list unique finmap to list nodup Qed Lemma elem of finmap of list 1 l list K A i x NoDup fst l i x l finmap of list l i Some x Proof induction l as j y l IH simpl by rewrite elem of nil rewrite NoDup cons elem of cons elem of list fmap intros Hl simplify map equality done destruct decide i j simplify map equality done destruct Hl by exists j x Qed Lemma elem of finmap of list 2 l list K A i x finmap of list l i Some x i x l Proof induction l as j y l IH simpl by rewrite lookup empty rewrite elem of cons destruct decide i j simplify map equality intuition congruence Qed Lemma elem of finmap of list l list K A i x NoDup fst l i x l finmap of list l i Some x Proof split auto using elem of finmap of list 1 elem of finmap of list 2 Qed Lemma not elem of finmap of list 1 l list K A i i fst l finmap of list l i None Proof rewrite elem of list fmap eq None not Some is Some alt intros Hi x destruct Hi exists i x simpl auto using elem of finmap of list 2 Qed Lemma not elem of finmap of list 2 l list K A i finmap of list l i None i fst l Proof induction l as j y l IH simpl rewrite elem of nil tauto rewrite elem of cons destruct decide i j simplify map equality by intuition Qed Lemma not elem of finmap of list l list K A i i fst l finmap of list l i None Proof split auto using not elem of finmap of list 1 not elem of finmap of list 2 Qed Lemma finmap of list proper l1 l2 list K A NoDup fst l1 Permutation l1 l2 finmap of list l1 finmap of list l2 Proof intros Hperm apply finmap eq intros i apply option eq intros x by rewrite elem of finmap of list rewrite Hperm Qed Lemma finmap of list inj l1 l2 list K A NoDup fst l1 NoDup fst l2 finmap of list l1 finmap of list l2 Permutation l1 l2 Proof intros Hl1l2 apply NoDup Permutation auto using NoDup fmap 1 fst intros i x by rewrite elem of finmap of list Hl1l2 Qed Lemma finmap of to list m M A finmap of list finmap to list m m Proof apply finmap eq intros i apply option eq intros x by rewrite elem of finmap of list elem of finmap to list by auto using finmap to list key nodup Qed Lemma finmap to of list l list K A NoDup fst l Permutation finmap to list finmap of list l l Proof auto using finmap of list inj finmap to list key nodup finmap of to list Qed Lemma finmap to list inj m1 m2 M A Permutation finmap to list m1 finmap to list m2 m1 m2 Proof intros rewrite finmap of to list m1 finmap of to list m2 auto using finmap of list proper finmap to list key nodup Qed Lemma finmap to list empty finmap to list nil K A Proof apply elem of nil inv intros i x rewrite elem of finmap to list apply lookup empty Some Qed Lemma finmap to list insert m M A i x m i None Permutation finmap to list i x m i x finmap to list m Proof intros apply finmap of list inj simpl apply finmap to list key nodup constructor auto using finmap to list key nodup rewrite elem of list fmap intros Hlookup subst simpl in rewrite elem of finmap to list in Hlookup congruence by rewrite finmap of to list Qed Lemma finmap of list nil finmap of list nil K A Proof done Qed Lemma finmap of list cons l list K A i x finmap of list i x l i x finmap of list l Proof done Qed Lemma finmap to list empty inv m M A Permutation finmap to list m m Proof rewrite finmap to list empty apply finmap to list inj Qed Lemma finmap to list insert inv m M A l i x Permutation finmap to list m i x l m i x finmap of list l Proof intros Hperm apply finmap to list inj assert NoDup fst i x l as Hnodup rewrite Hperm auto using finmap to list key nodup simpl in Hnodup rewrite NoDup cons in Hnodup destruct Hnodup rewrite Hperm finmap to list insert finmap to of list auto using not elem of finmap of list 1 Qed Properties of the forall predicate Section finmap forall Context P K A Prop Lemma finmap forall to list m finmap forall P m Forall curry P finmap to list m Proof rewrite Forall forall split intros Hforall i x rewrite elem of finmap to list by apply Hforall i x intros Hforall i x rewrite elem of finmap to list by apply Hforall i x Qed Global Instance finmap forall dec i x Decision P i x m Decision finmap forall P m Proof refine cast if decide Forall curry P finmap to list m by rewrite finmap forall to list Defined End finmap forall Properties of the merge operation Section merge with Context f option A option A option A Global Instance LeftId None f LeftId merge f Proof intros apply finmap eq intros by rewrite merge spec f lookup empty left id None f Qed Global Instance RightId None f RightId merge f Proof intros apply finmap eq intros by rewrite merge spec f lookup empty right id None f Qed Context PropHolds f None None None Lemma merge spec alt m1 m2 m i m i f m1 i m2 i merge f m1 m2 m Proof split intro subst apply merge spec intros Hlookup apply finmap eq intros rewrite Hlookup apply merge spec Qed Lemma merge commutative m1 m2 i f m1 i m2 i f m2 i m1 i merge f m1 m2 merge f m2 m1 Proof intros apply finmap eq intros by rewrite merge spec f Qed Global Instance Commutative f Commutative merge f Proof intros apply merge commutative intros by apply commutative f Qed Lemma merge associative m1 m2 m3 i f m1 i f m2 i m3 i f f m1 i m2 i m3 i merge f m1 merge f m2 m3 merge f merge f m1 m2 m3 Proof intros apply finmap eq intros by rewrite merge spec f Qed Global Instance Associative f Associative merge f Proof intros apply merge associative intros by apply associative f Qed Lemma merge idempotent m1 i f m1 i m1 i m1 i merge f m1 m1 m1 Proof intros apply finmap eq intros by rewrite merge spec f Qed Global Instance Idempotent f Idempotent merge f Proof intros apply merge idempotent intros by apply idempotent f Qed End merge with Properties on the intersection forall relation Section intersection forall Context R relation A Global Instance finmap intersection forall sym Symmetric R Symmetric finmap intersection forall R Proof firstorder auto Qed Lemma finmap intersection forall empty l m M A finmap intersection forall R m Proof intros by simpl map Qed Lemma finmap intersection forall empty r m M A finmap intersection forall R m Proof intros by simpl map Qed Due to the finiteness of finite maps we can extract a witness are property does not hold for the intersection Lemma finmap not intersection forall x y Decision R x y m1 m2 M A finmap intersection forall R m1 m2 i x1 x2 m1 i Some x1 m2 i Some x2 R x1 x2 Proof split intros Hdisjoint set Pi i x1 x2 m1 i Some x1 m2 i Some x2 R x1 x2 assert i Decision Pi i intros i unfold Decision Pi destruct m1 i as x1 m2 i as x2 try by left destruct decide R x1 x2 naive solver intuition congruence destruct decide cexists Pi dom listset m1 dom listset m2 as i Hdom Hi Hi rewrite elem of intersection in Hdom rewrite elem of dom listset is Some alt in Hdom destruct Hdom as x1 x2 exists i x1 x2 auto destruct Hdisjoint intros i x1 x2 Hx1 Hx2 apply dec stable intros HP destruct Hi exists i rewrite elem of intersection elem of dom listset intuition eauto congruence intros i x1 x2 Hx1 Hx2 Hx1x2 Hdisjoint by apply Hx1x2 Hdisjoint i x1 x2 Qed End intersection forall Properties on the disjoint maps Lemma finmap disjoint alt m1 m2 M A m1 m2 i m1 i None m2 i None Proof split intros Hm1m2 i specialize Hm1m2 i destruct m1 i m2 i naive solver Qed Lemma finmap not disjoint m1 m2 M A m1 m2 i x1 x2 m1 i Some x1 m2 i Some x2 Proof unfold disjoint finmap disjoint rewrite finmap not intersection forall naive solver right auto Qed Global Instance Symmetric disjoint M A Proof apply finmap intersection forall sym auto Qed Lemma finmap disjoint empty l m M A m Proof apply finmap intersection forall empty l Qed Lemma finmap disjoint empty r m M A m Proof apply finmap intersection forall empty r Qed Lemma finmap disjoint weaken m1 m1 m2 m2 M A m1 m2 m1 m1 m2 m2 m1 m2 Proof intros Hdisjoint Hm1 Hm2 i x1 x2 Hx1 Hx2 destruct Hdisjoint i x1 x2 auto Qed Lemma finmap disjoint weaken l m1 m1 m2 M A m1 m2 m1 m1 m1 m2 Proof eauto using finmap disjoint weaken Qed Lemma finmap disjoint weaken r m1 m2 m2 M A m1 m2 m2 m2 m1 m2 Proof eauto using finmap disjoint weaken Qed Lemma finmap disjoint Some l m1 m2 M A i x m1 m2 m1 i Some x m2 i None Proof intros Hdisjoint rewrite eq None not Some is Some alt intros x2 by apply Hdisjoint i x x2 Qed Lemma finmap disjoint Some r m1 m2 M A i x m1 m2 m2 i Some x m1 i None Proof rewrite symmetry iff apply finmap disjoint Some l Qed Lemma finmap disjoint singleton l m M A i x i x m m i None Proof split intro apply finmap disjoint Some l i x x by simpl map intros j y1 y2 destruct decide i j simplify map equality congruence Qed Lemma finmap disjoint singleton r m M A i x m i x m i None Proof by rewrite symmetry iff finmap disjoint singleton l Qed Lemma finmap disjoint singleton l 2 m M A i x m i None i x m Proof by rewrite finmap disjoint singleton l Qed Lemma finmap disjoint singleton r 2 m M A i x m i None m i x Proof by rewrite finmap disjoint singleton r Qed Properties of the union and intersection operation Section union intersection with Context f A A option A Lemma finmap union with Some m1 m2 i x y m1 i Some x m2 i Some y union with f m1 m2 i f x y Proof intros Hx Hy unfold union with finmap union with by rewrite merge spec Hx Hy Qed Lemma finmap union with Some l m1 m2 i x m1 i Some x m2 i None union with f m1 m2 i Some x Proof intros Hx Hy unfold union with finmap union with by rewrite merge spec Hx Hy Qed Lemma finmap union with Some r m1 m2 i y m1 i None m2 i Some y union with f m1 m2 i Some y Proof intros Hx Hy unfold union with finmap union with by rewrite merge spec Hx Hy Qed Global Instance LeftId union with M A f Proof unfold union with finmap

    Original URL path: http://robbertkrebbers.nl/research/ch2o/fossacs2013/fin_maps.html (2015-08-10)
    Open archived version from archive

  • Module pmap
    induction i simpl intuition Qed Local Hint Resolve Psingleton raw ne Lemma Psingleton raw wf A i x A Pmap wf Psingleton raw i x Proof induction i simpl intuition Qed Local Hint Resolve Psingleton raw wf Lemma Plookup raw singleton A i x A Psingleton raw i x i Some x Proof by induction i Qed Lemma Plookup raw singleton ne A i j x A i j Psingleton raw i x j None Proof revert j induction i intros simpl auto congruence Qed Definition Pnode canon l Pmap raw A o option A r Pmap raw A match l o r with Pleaf None Pleaf Pleaf Pnode l o r end Lemma Pnode canon wf l Pmap raw A o option A r Pmap raw A Pmap wf l Pmap wf r Pmap wf Pnode canon l o r Proof intros H1 H2 destruct H1 o H2 simpl intuition Qed Local Hint Resolve Pnode canon wf Lemma Pnode canon lookup xH l Pmap raw A o r Pmap raw A Pnode canon l o r 1 o Proof by destruct l o r Qed Lemma Pnode canon lookup xO l Pmap raw A o r Pmap raw A i Pnode canon l o r i 0 l i Proof by destruct l o r Qed Lemma Pnode canon lookup xI l Pmap raw A o r Pmap raw A i Pnode canon l o r i 1 r i Proof by destruct l o r Qed Ltac Pnode canon rewrite repeat rewrite Pnode canon lookup xH rewrite Pnode canon lookup xO rewrite Pnode canon lookup xI Instance Ppartial alter raw A PartialAlter positive A Pmap raw A fix go f i t struct t Pmap raw A match t with Pleaf match f None with None Pleaf Some x Psingleton raw i x end Pnode l o r match i with 1 Pnode canon l f o r i 0 Pnode canon partial alter go f i l o r i 1 Pnode canon l o partial alter go f i r end end Lemma Ppartial alter raw wf A f i t Pmap raw A Pmap wf t Pmap wf partial alter f i t Proof intros twf revert i induction twf unfold partial alter simpl case f None intuition intros simpl intuition intros simpl intuition Qed Instance Ppartial alter A PartialAlter positive A Pmap A λ f i t dexist partial alter f i t Ppartial alter raw wf f i proj2 dsig t Lemma Plookup raw alter A f i t Pmap raw A partial alter f i t i f t i Proof revert i induction t intros i change match f None with Some x Psingleton raw i x None Pleaf end i f None destruct f None intros apply Plookup raw singleton by destruct i intros simpl by Pnode canon rewrite Qed Lemma Plookup raw alter ne A f i j t Pmap raw A i j partial alter f i t

    Original URL path: http://robbertkrebbers.nl/research/ch2o/fossacs2013/pmap.html (2015-08-10)
    Open archived version from archive

  • Module nmap
    i t match i t with N0 NMap o t NMap f o t Npos p NMap o t NMap o partial alter f p t end Instance Nto list A FinMapToList N A Nmap A λ t match t with NMap o t option case λ x 0 x o fst map Npos finmap to list t end Instance Nmerge A Merge A Nmap A λ f t1 t2 match t1 t2 with NMap o1 t1 NMap o2 t2 NMap f o1 o2 merge f t1 t2 end Instance Nfmap FMap Nmap λ A B f t match t with NMap o t NMap fmap f o fmap f t end Instance FinMap N Nmap Proof split intros H f equal apply H 0 apply finmap eq intros i apply H Npos i by intros intros f t i simpl done apply lookup partial alter intros f t i j simpl try intuition congruence intros apply lookup partial alter ne congruence intros simpl done apply lookup fmap intros x t unfold finmap to list simpl constructor rewrite elem of list fmap by intros rewrite NoDup fmap apply finmap to list nodup rewrite NoDup fmap apply finmap to list nodup

    Original URL path: http://robbertkrebbers.nl/research/ch2o/fossacs2013/nmap.html (2015-08-10)
    Open archived version from archive