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 decidable
    P Prop dec Decision P bool if dec then true else false Lemma bool decide unpack P Prop dec Decision P bool decide P P Proof unfold bool decide by destruct dec Qed Lemma bool decide pack P Prop dec Decision P P bool decide P Proof unfold bool decide by destruct dec Qed Decidable Sigma types Leibniz equality on Sigma types requires the equipped proofs to be equal as Coq does not support proof irrelevance For decidable we propositions we define the type dsig P whose Leibniz equality is proof irrelevant That is x y dsig P x y x y Definition dsig P A Prop x A Decision P x x bool decide P x Definition proj2 dsig x A Decision P x x dsig P P x bool decide unpack proj2 sig x Definition dexist x A Decision P x x A p P x dsig P x bool decide pack p Lemma dsig eq A P A Prop dec x Decision P x x y dsig P x y x y Proof split destruct x y apply proj1 sig inj intro destruct x as x Hx y as y Hy simpl in subst f equal revert Hx Hy case bool decide P y by intros done Qed The following combinators are useful to create Decision proofs in combination with the refine tactic Notation cast if S if S then left else right Notation cast if and S1 S2 if S1 then cast if S2 else right Notation cast if and3 S1 S2 S3 if S1 then cast if and S2 S3 else right Notation cast if and4 S1 S2 S3 S4 if S1 then cast if and3 S2 S3 S4 else right Notation cast if or S1 S2 if S1 then left else cast if S2

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

  • Module orders
    Qed Context X Y A Decision X Y Global Instance preorder equiv dec slow X Y A Decision X Y 100 Global Instance preorder subset dec slow X Y A Decision X Y 100 Lemma subseteq inv X Y X Y X Y X Y Proof destruct decide Y X by right by left Qed End preorder Typeclasses Opaque preorder equiv Hint Extern 0 Equivalence class apply preorder equivalence typeclass instances Join semi lattices General purpose theorems on join semi lattices Section bounded join sl Context BoundedJoinSemiLattice A Hint Resolve subseteq empty subseteq union l subseteq union r union least Lemma union compat l x1 x2 y x1 x2 x1 x2 y Proof intros transitivity x2 auto Qed Lemma union compat r x1 x2 y x1 x2 x1 y x2 Proof intros transitivity x2 auto Qed Hint Resolve union compat l union compat r Lemma union compat x1 x2 y1 y2 x1 x2 y1 y2 x1 y1 x2 y2 Proof auto Qed Lemma union empty x x x Proof by apply union least Qed Lemma union comm x y x y y x Proof auto Qed Lemma union assoc 1 x y z x y z x y z Proof auto Qed Lemma union assoc 2 x y z x y z x y z Proof auto Qed Global Instance union proper Proper Proof unfold equiv preorder equiv split apply union compat simpl in tauto Qed Global Instance Idempotent Proof split eauto Qed Global Instance LeftId Proof split eauto Qed Global Instance RightId Proof split eauto Qed Global Instance Commutative Proof split apply union comm Qed Global Instance Associative Proof split apply union assoc 2 apply union assoc 1 Qed Lemma subseteq union X Y X Y X Y Y Proof repeat split eauto intros E rewrite E auto Qed Lemma subseteq union 1 X Y X Y X Y Y Proof apply subseteq union Qed Lemma subseteq union 2 X Y X Y Y X Y Proof apply subseteq union Qed Lemma equiv empty X X X Proof split eauto Qed Global Instance Proper eqlistA union list Proof induction 1 simpl done by apply union proper Qed Lemma empty union X Y X Y X Y Proof split intros E split apply equiv empty by transitivity X Y auto rewrite E intros E1 E2 by rewrite E1 E2 left id Qed Lemma empty list union Xs Xs Forall Xs Proof split induction Xs simpl rewrite empty union intuition induction 1 as E1 E2 simpl done by apply empty union Qed Context X Y A Decision X Y Lemma non empty union X Y X Y X Y Proof rewrite empty union destruct decide X intuition Qed Lemma non empty list union Xs Xs Exists Xs Proof rewrite empty list union apply not Forall Exists Qed End bounded join sl Meet semi lattices The dual of the above section but now for meet semi lattices Section meet sl Context MeetSemiLattice A Hint Resolve subseteq intersection l subseteq intersection r intersection

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

  • Module option
    A x option A a is Some x b x Some b b a x Some a Proof destruct 1 intros f equal auto Qed Equality on option is decidable Instance option eq dec dec x y A Decision x y x y option A Decision x y match x with Some a match y with Some b match dec a b with left H left f equal H right H right H injective Some end None right Some ne None end None match y with Some right None ne Some None left eq refl end end Monadic operations Instance option ret MRet option Some Instance option bind MBind option λ A B f x match x with Some a f a None None end Instance option join MJoin option λ A x match x with Some x x None None end Instance option fmap FMap option option map Instance option guard MGuard option λ P dec A x if dec then x else None Lemma option fmap is Some A B f A B x option A is Some x is Some f x Proof split inversion 1 done by destruct x Qed Lemma option fmap is None A B f A B x option A x None f x None Proof unfold fmap option fmap by destruct x Qed Lemma option bind assoc A B C f A option B g B option C x option A x f g x mbind g f Proof by destruct x simpl Qed Tactic Notation simplify option equality by tactic3 tac repeat match goal with first progress simpl in progress simplify equality H context mbind M option A A f o let Hx fresh in first let x fresh in evar x A let x eval unfold x in x in clear x assert o Some x as Hx by tac assert o None as Hx by tac rewrite Hx in H clear Hx H context fmap M option A A f o let Hx fresh in first let x fresh in evar x A let x eval unfold x in x in clear x assert o Some x as Hx by tac assert o None as Hx by tac rewrite Hx in H clear Hx H context match o with end match type of o with option A let Hx fresh in first let x fresh in evar x A let x eval unfold x in x in clear x assert o Some x as Hx by tac assert o None as Hx by tac rewrite Hx in H clear Hx end H mbind M option f o x match o with Some fail 1 None fail 1 idtac end match x with Some idtac None idtac fail 1 end destruct o eqn H x mbind M option f o match o with Some fail 1 None fail 1 idtac end match x with Some idtac None idtac fail 1 end destruct o eqn H fmap M option f o

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

  • Module list
    n length l n take n l k l take n length l k Proof revert n induction l intros simpl in f equal auto with lia Qed Lemma take ge l list A n length l n take n l l Proof revert n induction l intros simpl in f equal auto with lia Qed Lemma take take l list A n m take n take m l take min n m l Proof revert n m induction l intros simpl f equal auto Qed Lemma take idempotent l list A n take n take n l take n l Proof by rewrite take take Min min idempotent Qed Lemma take length l list A n length take n l min n length l Proof revert n induction l intros simpl f equal done Qed Lemma take length alt l list A n n length l length take n l n Proof rewrite take length apply Min min l Qed Lemma lookup take l list A n i i n take n l i l i Proof revert n i induction l intros n i trivial auto with lia destruct i simpl auto with arith Qed Lemma lookup take ge l list A n i n i take n l i None Proof revert n i induction l intros simpl auto with lia Qed Lemma take alter f A A l n i n i take n alter f i l take n l Proof intros apply list eq intros j destruct le lt dec n j by rewrite lookup take ge by rewrite lookup take list lookup alter ne by lia Qed Lemma take insert l list A n i x n i take n i x l take n l Proof take alter Lemma drop nil n drop n nil A Proof by destruct n Qed Lemma drop app l k list A drop length l l k k Proof induction l simpl f equal auto Qed Lemma drop app alt l k list A n n length l drop n l k k Proof intros Hn by rewrite Hn drop app Qed Lemma drop length l list A n length drop n l length l n Proof revert n by induction l intros i simpl f equal Qed Lemma drop all l list A drop length l l Proof induction l simpl auto Qed Lemma drop all alt l list A n n length l drop n l Proof intros subst by rewrite drop all Qed Lemma lookup drop l list A n i drop n l i l n i Proof revert n i induction l intros i simpl auto Qed Lemma drop alter f A A l n i i n drop n alter f i l drop n l Proof intros apply list eq intros j by rewrite lookup drop list lookup alter ne by lia Qed Lemma drop insert l list A n i x i n drop n i x l drop n l Proof drop alter Lemma replicate length n x A length replicate n x n Proof induction n simpl auto Qed Lemma lookup replicate n x A i i n replicate n x i Some x Proof revert i induction n intros naive solver auto with lia Qed Lemma lookup replicate inv n x y A i replicate n x i Some y y x i n Proof revert i induction n intros naive solver auto with lia Qed Lemma replicate plus n m x A replicate n m x replicate n x replicate m x Proof induction n simpl f equal auto Qed Lemma take replicate n m x A take n replicate m x replicate min n m x Proof revert m by induction n intros simpl f equal Qed Lemma take replicate plus n m x A take n replicate n m x replicate n x Proof by rewrite take replicate min l by lia Qed Lemma drop replicate n m x A drop n replicate m x replicate m n x Proof revert m by induction n intros simpl f equal Qed Lemma drop replicate plus n m x A drop n replicate n m x replicate m x Proof rewrite drop replicate f equal lia Qed Lemma resize spec l list A n x resize n x l take n l replicate n length l x Proof revert n induction l intros simpl f equal auto Qed Lemma resize 0 l list A x resize 0 x l Proof by destruct l Qed Lemma resize nil n x A resize n x replicate n x Proof rewrite resize spec rewrite take nil simpl f equal lia Qed Lemma resize ge l list A n x length l n resize n x l l replicate n length l x Proof intros by rewrite resize spec take ge Qed Lemma resize le l list A n x n length l resize n x l take n l Proof intros rewrite resize spec proj2 NPeano Nat sub 0 le by done simpl by rewrite app nil r Qed Lemma resize all l list A x resize length l x l l Proof intros by rewrite resize le take ge Qed Lemma resize all alt l list A n x n length l resize n x l l Proof intros subst by rewrite resize all Qed Lemma resize plus l list A n m x resize n m x l resize n x l resize m x drop n l Proof revert n m induction l intros simpl f equal auto by rewrite plus 0 r app nil r by rewrite replicate plus Qed Lemma resize plus eq l list A n m x length l n resize n m x l l replicate m x Proof intros subst by rewrite resize plus resize all drop all resize nil Qed Lemma resize app le l1 l2 list A n x n length l1 resize n x l1 l2 resize n x l1 Proof intros by rewrite resize le take app le by rewrite app length lia Qed Lemma resize app ge l1 l2 list A n x length l1 n resize n x l1 l2 l1 resize n length l1 x l2 Proof intros rewrite resize spec take app ge app assoc by done do 2 f equal rewrite app length lia Qed Lemma resize length l list A n x length resize n x l n Proof rewrite resize spec app length replicate length take length lia Qed Lemma resize replicate x A n m resize n x replicate m x replicate n x Proof revert m induction n intros simpl f equal auto Qed Lemma resize resize l list A n m x n m resize n x resize m x l resize n x l Proof revert n m induction l simpl intros by rewrite resize nil resize replicate intros simpl f equal auto with lia Qed Lemma resize idempotent l list A n x resize n x resize n x l resize n x l Proof by rewrite resize resize Qed Lemma resize take le l list A n m x n m resize n x take m l resize n x l Proof revert n m induction l intros simpl f equal auto with lia Qed Lemma resize take eq l list A n x resize n x take n l resize n x l Proof by rewrite resize take le Qed Lemma take resize l list A n m x take n resize m x l resize min n m x l Proof revert n m induction l intros simpl f equal auto using take replicate Qed Lemma take resize le l list A n m x n m take n resize m x l resize n x l Proof intros by rewrite take resize Min min l Qed Lemma take resize eq l list A n x take n resize n x l resize n x l Proof intros by rewrite take resize Min min l Qed Lemma take length resize l list A n x length l n take length l resize n x l l Proof intros by rewrite take resize le resize all Qed Lemma take length resize alt l list A n m x m length l m n take m resize n x l l Proof intros subst by apply take length resize Qed Lemma take resize plus l list A n m x take n resize n m x l resize n x l Proof by rewrite take resize min l by lia Qed Lemma drop resize le l list A n m x n m drop n resize m x l resize m n x drop n l Proof revert n m induction l simpl intros by rewrite drop nil resize nil drop replicate intros simpl try case match auto with lia Qed Lemma drop resize plus l list A n m x drop n resize n m x l resize m x drop n l Proof rewrite drop resize le by lia f equal lia Qed Section Forall Exists Context P A Prop Lemma Forall forall l Forall P l x x l P x Proof split induction 1 inversion 1 subst auto intros Hin induction l constructor apply Hin constructor apply IHl intros apply Hin by constructor Qed Lemma Forall nil Forall P True Proof done Qed Lemma Forall cons 1 x l Forall P x l P x Forall P l Proof by inversion 1 Qed Lemma Forall cons x l Forall P x l P x Forall P l Proof split by inversion 1 intros by constructor Qed Lemma Forall singleton x Forall P x P x Proof rewrite Forall cons Forall nil tauto Qed Lemma Forall app l1 l2 Forall P l1 l2 Forall P l1 Forall P l2 Proof split induction l1 inversion 1 intuition intros H induction H simpl intuition Qed Lemma Forall true l x P x Forall P l Proof induction l auto Qed Lemma Forall impl l Q A Prop Forall P l x P x Q x Forall Q l Proof intros H induction H auto Defined Lemma Forall delete l i Forall P l Forall P delete i l Proof intros H revert i by induction H intros i try constructor Qed Lemma Forall lookup l Forall P l i x l i Some x P x Proof rewrite Forall forall setoid rewrite elem of list lookup naive solver Qed Lemma Forall lookup 1 l i x Forall P l l i Some x P x Proof rewrite Forall lookup eauto Qed Lemma Forall alter f l i Forall P l x l i Some x P x P f x Forall P alter f i l Proof intros Hl revert i induction Hl simpl intros i constructor auto Qed Lemma Forall replicate n x P x Forall P replicate n x Proof induction n simpl constructor auto Qed Lemma Forall replicate eq n x A Forall x replicate n x Proof induction n simpl constructor auto Qed Lemma Exists exists l Exists P l x x l P x Proof split induction 1 as x y IH exists x split constructor done destruct IH as x exists x split by constructor done intros x Hin induction l by destruct not elem of nil x inversion Hin subst by left right auto Qed Lemma Exists inv x l Exists P x l P x Exists P l Proof inversion 1 intuition trivial Qed Lemma Exists app l1 l2 Exists P l1 l2 Exists P l1 Exists P l2 Proof split induction l1 inversion 1 intuition intros H H induction H simpl intuition induction l1 simpl intuition Qed Lemma Exists not Forall l Exists not P l Forall P l Proof induction 1 inversion clear 1 contradiction Qed Lemma Forall not Exists l Forall not P l Exists P l Proof induction 1 inversion clear 1 contradiction Qed Context dec x Decision P x Fixpoint Forall Exists dec l Forall P l Exists not P l Proof refine match l with left x l cast if and dec x Forall Exists dec l end clear Forall Exists dec abstract intuition Defined Lemma not Forall Exists l Forall P l Exists not P l Proof intro destruct Forall Exists dec l intuition Qed Global Instance Forall dec l Decision Forall P l match Forall Exists dec l with left H left H right H right Exists not Forall H end Fixpoint Exists Forall dec l Exists P l Forall not P l Proof refine match l with right x l cast if or dec x Exists Forall dec l end clear Exists Forall dec abstract intuition Defined Lemma not Exists Forall l Exists P l Forall not P l Proof intro destruct Exists Forall dec l intuition Qed Global Instance Exists dec l Decision Exists P l match Exists Forall dec l with left H left H right H right Forall not Exists H end End Forall Exists End general properties Section Forall2 Context A B P A B Prop Lemma Forall2 nil inv l k Forall2 P k k Proof by inversion 1 Qed Lemma Forall2 nil inv r k Forall2 P k k Proof by inversion 1 Qed Lemma Forall2 cons inv l1 l2 x1 x2 Forall2 P x1 l1 x2 l2 P x1 x2 Forall2 P l1 l2 Proof by inversion 1 Qed Lemma Forall2 cons inv l l1 k x1 Forall2 P x1 l1 k x2 l2 P x1 x2 Forall2 P l1 l2 k x2 l2 Proof inversion 1 subst eauto Qed Lemma Forall2 cons inv r k l2 x2 Forall2 P k x2 l2 x1 l1 P x1 x2 Forall2 P l1 l2 k x1 l1 Proof inversion 1 subst eauto Qed Lemma Forall2 cons nil inv l1 x1 Forall2 P x1 l1 False Proof by inversion 1 Qed Lemma Forall2 nil cons inv l2 x2 Forall2 P x2 l2 False Proof by inversion 1 Qed Lemma Forall2 flip l1 l2 Forall2 P l1 l2 Forall2 flip P l2 l1 Proof split induction 1 constructor auto Qed Lemma Forall2 length l1 l2 Forall2 P l1 l2 length l1 length l2 Proof induction 1 simpl auto Qed Lemma Forall2 impl Q A B Prop l1 l2 Forall2 P l1 l2 x y P x y Q x y Forall2 Q l1 l2 Proof intros H induction H auto Defined Lemma Forall2 unique l k1 k2 Forall2 P l k1 Forall2 P l k2 x y1 y2 P x y1 P x y2 y1 y2 k1 k2 Proof intros H revert k2 induction H inversion clear 1 intros f equal eauto Qed Lemma Forall2 Forall l Q A Prop l k Forall2 P l k Forall λ y x P x y Q x k Forall Q l Proof induction 1 inversion clear 1 eauto Qed Lemma Forall2 Forall r Q B Prop l k Forall2 P l k Forall λ x y P x y Q y l Forall Q k Proof induction 1 inversion clear 1 eauto Qed Lemma Forall2 lookup l1 l2 i x y Forall2 P l1 l2 l1 i Some x l2 i Some y P x y Proof intros H revert i induction H discriminate intros simpl in simplify equality eauto Qed Lemma Forall2 lookup l l1 l2 i x Forall2 P l1 l2 l1 i Some x y l2 i Some y P x y Proof intros H revert i induction H discriminate intros simpl in simplify equality eauto Qed Lemma Forall2 lookup r l1 l2 i y Forall2 P l1 l2 l2 i Some y x l1 i Some x P x y Proof intros H revert i induction H discriminate intros simpl in simplify equality eauto Qed Lemma Forall2 alter l f l1 l2 i Forall2 P l1 l2 x1 x2 l1 i Some x1 l2 i Some x2 P x1 x2 P f x1 x2 Forall2 P alter f i l1 l2 Proof intros Hl revert i induction Hl simpl intros i constructor auto Qed Lemma Forall2 alter r f l1 l2 i Forall2 P l1 l2 x1 x2 l1 i Some x1 l2 i Some x2 P x1 x2 P x1 f x2 Forall2 P l1 alter f i l2 Proof intros Hl revert i induction Hl simpl intros i constructor auto Qed Lemma Forall2 alter f g l1 l2 i Forall2 P l1 l2 x1 x2 l1 i Some x1 l2 i Some x2 P x1 x2 P f x1 g x2 Forall2 P alter f i l1 alter g i l2 Proof intros Hl revert i induction Hl simpl intros i constructor auto Qed Lemma Forall2 replicate l l n x Forall P x l length l n Forall2 P replicate n x l Proof intros Hl revert n induction Hl intros simplify equality constructor auto Qed Lemma Forall2 replicate r l n x Forall flip P x l length l n Forall2 P l replicate n x Proof intros Hl revert n induction Hl intros simplify equality constructor auto Qed Lemma Forall2 replicate n x1 x2 P x1 x2 Forall2 P replicate n x1 replicate n x2 Proof induction n simpl constructor auto Qed Lemma Forall2 take l1 l2 n Forall2 P l1 l2 Forall2 P take n l1 take n l2 Proof intros Hl1l2 revert n induction Hl1l2 intros simpl auto Qed Lemma Forall2 drop l1 l2 n Forall2 P l1 l2 Forall2 P drop n l1 drop n l2 Proof intros Hl1l2 revert n induction Hl1l2 intros simpl auto Qed Lemma Forall2 resize l1 l2 x1 x2 n P x1 x2 Forall2 P l1 l2 Forall2 P resize n x1 l1 resize n x2 l2 Proof intros rewrite resize spec Forall2 length l1 l2 by done auto using Forall2 app Forall2 take Forall2 replicate Qed Lemma Forall2 resize ge l l1 l2 x1 x2 n m x P x x2 n m Forall2 P resize n x1 l1 l2 Forall2 P resize m x1 l1 resize m x2 l2 Proof intros assert n length l2 by rewrite Forall2 length resize n x1 l1 l2 resize length rewrite le plus minus n m by done subst rewrite resize plus resize all drop all resize nil apply Forall2 app done apply Forall2 replicate r by rewrite resize length by apply Forall true Qed Lemma Forall2 resize ge r l1 l2 x1 x2 n m x3 P x1 x3 n m Forall2 P l1 resize n x2 l2 Forall2 P resize m x1 l1 resize m x2 l2 Proof intros assert n length l1 by rewrite Forall2 length l1 resize n x2 l2 resize length rewrite le plus minus n m by done subst rewrite resize plus resize all drop all resize nil apply Forall2 app done apply Forall2 replicate l by rewrite resize length by apply Forall true Qed Lemma Forall2 trans C Q B C Prop R A C Prop l1 l2 l3 x1 x2 x3 P x1 x2 Q x2 x3 R x1 x3 Forall2 P l1 l2 Forall2 Q l2 l3 Forall2 R l1 l3 Proof intros Hl1l2 revert l3 induction Hl1l2 inversion clear 1 eauto Qed Lemma Forall2 Forall Q A A Prop l Forall λ x Q x x l Forall2 Q l l Proof induction 1 constructor auto Qed Global Instance Forall2 dec x1 x2 Decision P x1 x2 l1 l2 Decision Forall2 P l1 l2 Proof refine fix go l1 l2 Decision Forall2 P l1 l2 match l1 l2 with left x1 l1 x2 l2 cast if and decide P x1 x2 go l1 l2 right end clear go abstract first by constructor by inversion 1 Defined End Forall2 Section Forall2 order Context A R relation A Global Instance PreOrder R PreOrder Forall2 R Proof split intros l induction l by constructor intros apply Forall2 trans apply transitivity Qed Global Instance AntiSymmetric R AntiSymmetric Forall2 R Proof induction 2 inversion clear 1 f equal auto Qed End Forall2 order Ltac decompose elem of list repeat match goal with H x by destruct not elem of nil x H apply elem of cons in H destruct H H apply elem of app in H destruct H end Ltac decompose Forall repeat match goal with H Forall clear H H Forall rewrite Forall cons in H destruct H H Forall rewrite Forall app in H destruct H H Forall2 clear H H Forall2 destruct Forall2 cons nil inv H H Forall2 destruct Forall2 nil cons inv H H Forall2 l apply Forall2 nil inv l in H subst l H Forall2 l apply Forall2 nil inv r in H subst l H Forall2 apply Forall2 cons inv in H destruct H H Forall2 l apply Forall2 cons inv l in H destruct H as subst l H Forall2 l apply Forall2 cons inv r in H destruct H as subst l end Theorems on the prefix and suffix predicates Section prefix postfix Context A Type Global Instance PreOrder prefix of A Proof split intros eexists by rewrite app nil r intros k1 k2 exists k1 k2 subst by rewrite app assoc Qed Lemma prefix of nil l list A prefix of l Proof by exists l Qed Lemma prefix of nil not x l list A prefix of x l Proof by intros k E Qed Lemma prefix of cons x y l1 l2 list A x y prefix of l1 l2 prefix of x l1 y l2 Proof intros k E exists k by subst Qed Lemma prefix of cons inv 1 x y l1 l2 list A prefix of x l1 y l2 x y Proof intros k E by injection E Qed Lemma prefix of cons inv 2 x y l1 l2 list A prefix of x l1 y l2 prefix of l1 l2 Proof intros k E exists k by injection E Qed Lemma prefix of app l l1 l2 l3 list A prefix of l1 l3 l2 prefix of l1 l2 Proof intros k red exists l3 k subst by rewrite app assoc Qed Lemma prefix of app r l1 l2 l3 list A prefix of l1 l2 prefix of l1 l2 l3 Proof intros k exists k l3 subst by rewrite app assoc Qed Global Instance PreOrder suffix of A Proof split intros by eexists intros k1 k2 exists k2 k1 subst by rewrite app assoc Qed Lemma prefix suffix reverse l1 l2 list A prefix of l1 l2 suffix of reverse l1 reverse l2 Proof split intros k E exists reverse k by rewrite E reverse app by rewrite reverse involutive l2 E reverse app reverse involutive Qed Lemma suffix prefix reverse l1 l2 list A suffix of l1 l2 prefix of reverse l1 reverse l2 Proof by rewrite prefix suffix reverse reverse involutive Qed Lemma suffix of nil l list A suffix of l Proof exists l by rewrite app nil r Qed Lemma suffix of nil inv l list A suffix of l l Proof by intros simplify list equality Qed Lemma suffix of cons nil inv x l list A suffix of x l Proof by intros Qed Lemma suffix of app l1 l2 k list A suffix of l1 l2 suffix of l1 k l2 k Proof intros k E exists k subst by rewrite app assoc Qed Lemma suffix of snoc inv 1 x y l1 l2 list A suffix of l1 x l2 y x y Proof rewrite suffix prefix reverse reverse snoc by apply prefix of cons inv 1 Qed Lemma suffix of snoc inv 2 x y l1 l2 list A suffix of l1 x l2 y suffix of l1 l2 Proof rewrite suffix prefix reverse reverse snoc by apply prefix of cons inv 2 Qed Lemma suffix of cons l l1 l2 list A x suffix of x l1 l2 suffix of l1 l2 Proof intros k exists k x subst by rewrite app assoc Qed Lemma suffix of app l l1 l2 l3 list A suffix of l3 l1 l2 suffix of l1 l2 Proof intros k exists k l3 subst by rewrite app assoc Qed Lemma suffix of cons r l1 l2 list A x suffix of l1 l2 suffix of l1 x l2 Proof intros k exists x k by subst Qed Lemma suffix of app r l1 l2 l3 list A suffix of l1 l2 suffix of l1 l3 l2 Proof intros k exists l3 k subst by rewrite app assoc Qed Lemma suffix of cons inv l1 l2 list A x y suffix of x l1 y l2 x l1 y l2 suffix of x l1 l2 Proof intros k E by left right simplify equality by apply suffix of app r Qed Lemma suffix of cons not x l list A suffix of x l l Proof intros discriminate list equality Qed Context x y A Decision x y Fixpoint strip prefix l1 l2 list A list A list A list A match l1 l2 with l2 l2 l1 l1 x l1 y l2 if decide rel x y then fst map x strip prefix l1 l2 else x l1 y l2 end Global Instance prefix of dec l1 l2 list A Decision prefix of l1 l2 fix go l1 l2 match l1 l2 return prefix of l1 l2 prefix of l1 l2 with left prefix of nil right prefix of nil not x l1 y l2 match decide rel x y with left Exy match go l1 l2 with left Hl1l2 left prefix of cons Exy Hl1l2 right Hl1l2 right Hl1l2 prefix of cons inv 2 end right Exy right Exy prefix of cons inv 1 end end Global Instance suffix of dec l1 l2 list A Decision suffix of l1 l2 Proof refine cast if decide rel prefix of reverse l1 reverse l2 abstract by rewrite suffix prefix reverse Defined End prefix postfix The simplify suffix of tactic removes suffix of hypotheses that are tautologies and simplifies suffix of hypotheses involving and Ltac simplify suffix of repeat match goal with H suffix of destruct suffix of cons not H H suffix of apply suffix of nil inv in H H suffix of destruct suffix of cons inv H clear H H suffix of x x clear H H suffix of x x clear H H suffix of x x clear H progress simplify equality end The solve suffix of tactic tries to solve goals involving suffix of It uses simplify suffix of to simplify hypotheses and tries to solve suffix of conclusions This tactic either fails or proves the goal Ltac solve suffix of solve intuition repeat match goal with done progress simplify suffix of suffix of apply suffix of nil suffix of reflexivity suffix of apply suffix of cons r suffix of apply suffix of app r H suffix of False destruct H end Hint Extern 0 PropHolds suffix of unfold PropHolds solve suffix of typeclass instances Folding lists Notation foldr fold right Notation foldr app fold right app Lemma foldr permutation A B R relation B Equivalence R f A B B b B Proper R R f Hf a1 a2 b R f a1 f a2 b f a2 f a1 b Proper Permutation R foldr f b Proof induction 1 simpl done by f equiv apply Hf etransitivity eauto Qed We redefine foldl with the arguments in the same order as in Haskell Definition foldl A B f A B A A list B A fix go a l match l with a x l go f a x l end Lemma foldl app A B f A B A l k list B a A foldl f a l k foldl f foldl f a l k Proof revert a induction l simpl auto Qed Monadic operations Instance list ret MRet list λ A x x nil A Instance list fmap A B f A B FMapD list f fix go l list A match l with x l f x fmap f go l end Instance list bind A B f A list B MBindD list f fix go l list A match l with x l f x mbind f go l end Instance list join MJoin list fix go A ls list list A list A match ls with l ls l mjoin go ls end Definition mapM MBind M MRet M A B f A M B list A M list B fix go l match l with mret x l y f x k go l mret y k end Section list fmap Context A B Type f A B Lemma list fmap compose C g B C l g f l g f l Proof induction l simpl f equal auto Qed Lemma list fmap ext g A B l list A x f x g x fmap f l fmap g l Proof intro induction l simpl f equal auto Qed Lemma list fmap ext alt g A B l list A Forall λ x f x g x l fmap f l fmap g l Proof split induction 1 simpl f equal auto induction l simpl constructor simplify equality auto Qed Global Instance Injective f Injective fmap f Proof intros l1 induction l1 as x l1 IH by intros intros simpl intros f equal simplify equality auto Qed Lemma fmap app l1 l2 f l1 l2 f l1 f l2 Proof induction l1 simpl by f equal Qed Lemma fmap cons inv y l k f l y k x l y f x l x l Proof intros destruct l simpl simplify equality eauto Qed Lemma fmap app inv l k1 k2 f l k1 k2 l1 l2 k1 f l1 k2 f l2 l l1 l2 Proof revert l induction k1 as y k1 IH simpl intros l by eexists l intros x l simpl simplify equality destruct IH l as l1 l2 subst done by exists x l1 l2 Qed Lemma fmap length l length f l length l Proof induction l simpl by f equal Qed Lemma fmap reverse l f reverse l reverse f l Proof induction l simpl done by rewrite reverse cons fmap app IHl Qed Lemma fmap replicate n x f replicate n x replicate n f x Proof induction n simpl f equal auto Qed Lemma list lookup fmap l i f l i f l i Proof revert i induction l by intros Qed Lemma list lookup fmap inv l i x f l i Some x y x f y l i Some y Proof intros Hi rewrite list lookup fmap in Hi destruct l i eqn simplify equality eauto Qed Lemma list alter fmap g A A h B B l i Forall λ x f g x h f x l f alter g i l alter h i f l Proof intros Hl revert i induction Hl intros i simpl f equal auto Qed Lemma elem of list fmap 1 l x x l f x f l Proof induction 1 simpl rewrite elem of cons intuition Qed Lemma elem of list fmap 1 alt l x y x l y f x y f l Proof intros subst by apply elem of list fmap 1 Qed Lemma elem of list fmap 2 l x x f l y x f y y l Proof induction l as y l IH simpl intros decompose elem of list exists y split done by left destruct IH as z done exists z split done by right Qed Lemma elem of list fmap l x x f l y x f y y l Proof firstorder eauto using elem of list fmap 1 alt elem of list fmap 2 Qed Lemma NoDup fmap 1 l list A NoDup f l NoDup l Proof induction l simpl inversion clear 1 constructor auto rewrite elem of list fmap in naive solver Qed Lemma NoDup fmap 2 Injective f l list A NoDup l NoDup f l Proof induction 1 simpl constructor trivial rewrite elem of list fmap intros y Hxy apply injective f in Hxy by subst Qed Lemma NoDup fmap Injective f l list A NoDup f l NoDup l Proof split auto using NoDup fmap 1 NoDup fmap 2 Qed Global Instance fmap Permutation proper Proper Permutation Permutation fmap f Proof induction 1 simpl econstructor eauto Qed Lemma Forall fmap l list A P B Prop Forall P f l Forall P f l Proof split induction l inversion clear 1 constructor auto Qed Lemma Forall2 fmap l C P B C Prop l1 l2 Forall2 P f l1 l2 Forall2 P f l1 l2 Proof split revert l2 induction l1 inversion clear 1 constructor auto Qed Lemma Forall2 fmap r C P C B Prop l1 l2 Forall2 P l1 f l2 Forall2 λ x P x f l1 l2 Proof split revert l1 induction l2 inversion clear 1 constructor auto Qed Lemma Forall2 fmap 1 C D g C D P B D Prop l1 l2 Forall2 P f l1 g l2 Forall2 λ x1 x2 P f x1 g x2 l1 l2 Proof revert l2 induction l1 intros inversion clear 1 auto Qed Lemma Forall2 fmap 2 C D g C D P B D Prop l1 l2 Forall2 λ x1 x2 P f x1 g x2 l1 l2 Forall2 P f l1 g l2 Proof induction 1 simpl auto Qed Lemma Forall2 fmap C D g C D P B D Prop l1 l2 Forall2 P f l1 g l2 Forall2 λ x1 x2 P f x1 g x2 l1 l2 Proof split auto using Forall2 fmap 1 Forall2 fmap 2 Qed Lemma mapM fmap Some g B option A l list A x g f x Some x mapM g f l Some l Proof intros by induction l simpl simplify option equality Qed Lemma mapM fmap Some inv g B option A l list A k list B x y g y Some x y f x mapM g k Some l k f l Proof intros Hgf revert l induction k as y k intros x l simplify option equality f equiv eauto Qed Lemma mapM Some g B option A l k Forall2 λ x y g x Some y l k mapM g l Some k Proof by induction 1 simplify option equality Qed Lemma Forall2 impl mapM P B A Prop g B option A l k Forall λ x y g x Some y P x y l mapM g l Some k Forall2 P l k Proof intros Hl revert k induction Hl intros simplify option equality eauto Qed End list fmap Lemma NoDup fmap fst A B l list A B x y1 y2 x y1 l x y2 l y1 y2 NoDup l NoDup fst l Proof intros Hunique induction 1 as x1 y1 l Hin Hnodup IH simpl constructor rewrite elem of list fmap intros x2 y2 simpl in subst destruct Hin rewrite Hunique x2 y1 y2 rewrite elem of cons auto apply IH intros eapply Hunique rewrite elem of cons eauto Qed Section list bind Context A B Type f A list B Lemma bind app l1 l2 list A l1 l2 f l1 f l2 f Proof induction l1 simpl done by rewrite app assoc IHl1 Qed Lemma elem of list bind x B l list A x l f y x f y y l Proof split induction l as y l IH simpl intros decompose elem of list exists y split done by left destruct IH as z done exists z split done by right intros y Hx Hy induction Hy simpl rewrite elem of app intuition Qed Lemma Forall2 bind C D g C list D P B D Prop l1 l2

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

  • Module vector
    f equal eauto using vcons inj 1 vcons inj 2 Defined Similar to fin we provide an inversion principle that keeps the length fixed We define a tactic inv vec v to perform case analysis on v using this inversion principle Notation vec 0 inv Vector case0 Definition vec S inv A n P vec A S n Type Hcons x v P x v v P v Proof revert P Hcons refine match v with tt x v λ P Hcons Hcons x v end Defined Ltac inv vec v match type of v with vec 0 revert dependent v match goal with v P v apply vec 0 inv P end vec S n revert dependent v match goal with v P v apply vec S inv P end end The following tactic performs case analysis on all hypotheses of the shape fin 0 fin S n vec A 0 and vec A S n until no further case analyses are possible Ltac inv all vec fin block goal repeat match goal with v vec inv vec v intros i fin inv fin i intros end unblock goal We define a coercion from vec to list and show that it preserves the operations on vectors We also define a function to go in the other way but do not define it as a coercion as it would otherwise introduce ambiguity Fixpoint vec to list A n v vec A n list A match v with x v x vec to list v end Coercion vec to list vec list Notation list to vec Vector of list Lemma vec to list cons A n x v vec A n vec to list x v x vec to list v Proof done Qed Lemma vec to list app A n m v vec A n w vec A m vec to list v w vec to list v vec to list w Proof by induction v simpl f equal Qed Lemma vec to list of list A l list A vec to list list to vec l l Proof by induction l simpl f equal Qed Lemma vec to list length A n v vec A n length vec to list v n Proof induction v simpl by f equal Qed Lemma vec to list inj1 A n m v vec A n w vec A m vec to list v vec to list w n m Proof revert m w induction v intros simpl in simplify equality f equal eauto Qed Lemma vec to list inj2 A n v vec A n w vec A n vec to list v vec to list w v w Proof revert w induction v intros w inv vec w intros simpl in simplify equality f equal eauto Qed Lemma vlookup middle A n m v vec A n w vec A m x i fin n S m x v x w i Proof induction v simpl by eexists 0 fin destruct

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

  • Module numbers
    Notation x y z x y y z N N scope Notation x y z x y y z N N scope Notation N le only parsing N scope Notation N lt only parsing N scope Infix div N div at level 35 N scope Infix mod N modulo at level 35 N scope Instance Injective Npos Proof by injection 1 Qed Instance N eq dec x y N Decision x y N eq dec Program Instance N le dec x y N Decision x y N match Ncompare x y with Gt right left end Next Obligation congruence Qed Program Instance N lt dec x y N Decision x y N match Ncompare x y with Lt left right end Next Obligation congruence Qed Instance N inhabited Inhabited N populate 1 N Infix Z le Z scope Notation x y z x y y z Z Z scope Notation x y z x y y z Z Z scope Notation x y z x y y z Z Z scope Notation x y z x y y z Z Z scope Notation Z le only parsing Z scope Notation Z lt only parsing Z scope Infix div Z div at level 35 Z scope Infix mod Z modulo at level 35 Z scope Instance Z eq dec x y Z Decision x y Z eq dec Instance Z le dec x y Z Decision x y Z Z le dec Instance Z lt dec x y Z Decision x y Z Z lt dec Instance Z inhabited Inhabited Z populate 1 Z Conversions The function Z to option N converts an integer x into a natural number by giving None in case x is negative Definition Z to option N x Z option N match x with Z0 Some N0 Zpos p Some Npos p Zneg None end The function Z decide converts a decidable proposition P into an integer by yielding one if P holds and zero if P does not Definition Z decide P Prop dec Decision P Z if dec then 1 else 0 Z The function Z decide rel is the more efficient variant of Z decide when used for binary relations It yields one if R x y and zero if not R x y Definition Z decide rel A B R A B Prop dec x y Decision R x y x A y B Z if dec x y then 1 else 0 Z Some correspondence lemmas between nat and N that are not part of the standard library We declare a hint database natify to rewrite a goal involving N into a corresponding variant involving nat Lemma N to nat lt x y N to nat x N to nat y x y N Proof by rewrite N compare lt iff nat compare lt N2Nat inj compare Qed Lemma N to nat le x y N to nat x N to nat y x y N Proof by rewrite N compare

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

  • Module ars
    nsteps R n m x z Proof induction 1 simpl eauto with ars Qed Lemma nsteps r n x y z nsteps R n x y R y z nsteps R S n x z Proof induction 1 eauto with ars Qed Lemma nsteps rtc n x y nsteps R n x y rtc R x y Proof induction 1 eauto with ars Qed Lemma rtc nsteps x y rtc R x y n nsteps R n x y Proof induction 1 firstorder eauto with ars Qed Lemma bsteps once n x y R x y bsteps R S n x y Proof eauto with ars Qed Lemma bsteps plus r n m x y bsteps R n x y bsteps R n m x y Proof induction 1 simpl eauto with ars Qed Lemma bsteps weaken n m x y n m bsteps R n x y bsteps R m x y Proof intros rewrite Minus le plus minus n m auto using bsteps plus r Qed Lemma bsteps plus l n m x y bsteps R n x y bsteps R m n x y Proof apply bsteps weaken auto with arith Qed Lemma bsteps S n x y bsteps R n x y bsteps R S n x y Proof apply bsteps weaken lia Qed Lemma bsteps trans n m x y z bsteps R n x y bsteps R m y z bsteps R n m x z Proof induction 1 simpl eauto using bsteps plus l with ars Qed Lemma bsteps r n x y z bsteps R n x y R y z bsteps R S n x z Proof induction 1 eauto with ars Qed Lemma bsteps rtc n x y bsteps R n x y rtc R x y Proof induction 1 eauto with ars Qed Lemma rtc bsteps x y rtc R x y n bsteps R n x y Proof induction 1 exists 0 constructor naive solver eauto with ars Qed Lemma bsteps ind r P nat A Prop x A Prefl n P n x Pstep n y z bsteps R n x y R y z P n y P S n z n z bsteps R n x z P n z Proof cut m y z bsteps R m y z n bsteps R n x y m n m m n m P m y P n m z intros help change n with 0 n eauto with ars induction 1 as m x y z p2 p3 IH by eauto with arith intros n p1 H rewrite plus n Sm apply IH S n by eauto using bsteps r intros m lia apply Pstep with x apply bsteps weaken with n intuition lia done apply H intuition lia Qed Global Instance tc trans Transitive tc R Proof red induction 1 eauto with ars Qed Lemma tc r x y z tc R x y R y z tc R x z Proof intros etransitivity

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

  • Module collections
    Y Z X Z Y Z Proof esolve elem of Qed Lemma elem of intersection with list f A A option A Xs Y x x intersection with list f Y Xs xs y Forall2 xs Xs y Y foldr λ x f x Some y xs Some x Proof split revert x induction Xs simpl intros x HXs eexists x intuition rewrite elem of intersection with in HXs destruct HXs as x1 x2 Hx1 Hx2 destruct IHXs x2 as xs y hy trivial eexists x1 xs y intuition simplify option equality auto intros xs y Hxs Hx revert x Hx induction Hxs intros simplify option equality done rewrite elem of intersection with naive solver Qed Lemma intersection with list ind P Q A Prop f Xs Y y y Y P y Forall λ X x x X Q x Xs x y z Q x P y f x y Some z P z x x intersection with list f Y Xs P x Proof intros HY HXs Hf induction Xs simplify option equality done intros x Hx rewrite elem of intersection with in Hx decompose Forall destruct Hx as eauto Qed Context X Y C Decision X Y Lemma not elem of intersection x X Y x X Y x X x Y Proof rewrite elem of intersection destruct decide x X tauto Qed Lemma not elem of difference x X Y x X Y x X x Y Proof rewrite elem of difference destruct decide x Y tauto Qed Lemma union difference X Y X Y Y X Y X Proof split intros x rewrite elem of union elem of difference destruct decide x X intuition intuition Qed Lemma non empty difference X Y X Y Y X Proof intros HXY1 HXY2 Hdiff destruct HXY2 intros x destruct decide x X esolve elem of Qed End collection Sets without duplicates up to an equivalence Section no dup Context SimpleCollection A B R relation A Equivalence R Definition elem of upto x A X B y y X R x y Definition no dup X B x y x X y X R x y x y Global Instance Proper iff elem of upto x Proof intros E unfold elem of upto by setoid rewrite E Qed Global Instance Proper R iff elem of upto Proof intros E1 E2 split intros z exists z rewrite E1 E2 intuition rewrite E1 E2 intuition Qed Global Instance Proper iff no dup Proof firstorder Qed Lemma elem of upto elem of x X x X elem of upto x X Proof unfold elem of upto esolve elem of Qed Lemma elem of upto empty x elem of upto x Proof unfold elem of upto esolve elem of Qed Lemma elem of upto singleton x y elem of upto x y R x y Proof unfold elem of upto esolve elem of Qed Lemma elem of upto union X Y x elem of upto x X Y elem of upto x

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