Project documentation
Returns a boolean witnessing the sortedness of a HeapLang list. acc is an option of the last value in the list. -/ def checkSorted : Val := hl_val% rec check acc l := match l with | none() => #true | some(x) => let p := !x; let head := fst(p); let tail := snd(p); let ok := (match acc with | none() => #true | some(v) => v ≤ head); ok && check (some(head)...
Exact Lean statement
theorem wp_checkSorted (v vacc : Val) (l : List Int) (Φ : Val → IProp GF) :
isList (GF := GF) v l -∗
⌜List.Pairwise (· ≤ ·) l⌝ -∗
⌜vacc = hl_val(none()) ∨ ∃ va : Int, vacc = hl_val(some(#va)) ∧ ∀ lv ∈ l, va ≤ lv⌝ -∗
(∀ bv, isList v l -∗ ⌜bv = hl_val(#true)⌝ -∗ Φ bv) -∗
WP hl(&checkSorted &vacc &v) {{ Φ }}Formal artifact
Lean source
theorem wp_checkSorted (v vacc : Val) (l : List Int) (Φ : Val → IProp GF) : isList (GF := GF) v l -∗ ⌜List.Pairwise (· ≤ ·) l⌝ -∗ ⌜vacc = hl_val(none()) ∨ ∃ va : Int, vacc = hl_val(some(#va)) ∧ ∀ lv ∈ l, va ≤ lv⌝ -∗ (∀ bv, isList v l -∗ ⌜bv = hl_val(#true)⌝ -∗ Φ bv) -∗ WP hl(&checkSorted &vacc &v) {{ Φ }} := by iintro H %hsorted %hinv HΦ iloeb as IH generalizing %vacc %l %v %hsorted %hinv wp_rec; wp_pures cases l with | nil => icases isList_nil $$ H with %heq; subst heq wp_pures imodintro iapply HΦ $$ H itrivial | cons hd tl => icases isList_cons $$ H with ⟨%loc, %tlv, %heq, Hpt, Htl⟩ subst heq wp_pures wp_bind !_ iapply wp_load $$ Hpt iintro !> Hpt rcases hinv with rfl | ⟨va, rfl, hva⟩ · wp_pures iapply IH $$ %_ %tl %_ %((List.pairwise_cons.mp hsorted).2) %(Or.inr ⟨hd, rfl, fun lv h => (List.pairwise_cons.mp hsorted).1 lv h⟩) Htl iintro %bv Hl %hb iapply HΦ $$ [Hpt Hl] · rw [isList] iexists loc, tlv iframe itrivial itrivial · wp_pures rw [decide_eq_true (hva hd List.mem_cons_self)] wp_pures iapply IH $$ %_ %tl %_ %((List.pairwise_cons.mp hsorted).2) %(.inr ⟨hd, rfl, (List.pairwise_cons.mp hsorted).1⟩) Htl iintro %bv Hl %hb iapply HΦ $$ [Hpt Hl] · rw [isList] iexists loc, tlv iframe itrivial itrivial- Project
- Iris-Lean
- License
- Apache-2.0
- Commit
- 37f53e0ac065
- Source
- Iris/Iris/HeapLang/Lib/Quicksort.lean:300-345
Reuse this declaration
Bring the exact result into your workflow
The import identifies the source module. Your project still needs the pinned package dependency shown on this page.
What this badge means
This completion status comes from the project or community source. It has not yet been represented here as an independent rebuild and axiom audit.
Continue in this project
Related declarations
Co Pset Raw eq
CoPset.coPsetRaw_eq
Plain-language statement
Two CoPsetRaw trees are equal if they have the same membership function and both are well-formed.
Source project: Iris-Lean
Person-level attribution pending.
Inj on of nodup map
FromMathlib.inj_on_of_nodup_map
Plain-language statement
NB. Copied from Mathlib
Source project: Iris-Lean
Person-level attribution pending.
Big Op L hom weak
Iris.Algebra.BigOpL.bigOpL_hom_weak
Plain-language statement
Weak monoid homomorphisms distribute over non-empty big ops.
Source project: Iris-Lean
Person-level attribution pending.