All proofs
Project-declaredLean 4.32.1 · null

Wp check Sorted

Iris.HeapLang.Quicksort.wp_checkSorted

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

Canonical source
Full Lean sourceLean 4
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

Project-declaredLean 4.32.1

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.

separation logicprogram logicsemantics

Source project: Iris-Lean

Person-level attribution pending.

View proof record
Project-declaredLean 4.32.1

Inj on of nodup map

FromMathlib.inj_on_of_nodup_map

Plain-language statement

NB. Copied from Mathlib

separation logicprogram logicsemantics

Source project: Iris-Lean

Person-level attribution pending.

View proof record
Project-declaredLean 4.32.1

Big Op L hom weak

Iris.Algebra.BigOpL.bigOpL_hom_weak

Plain-language statement

Weak monoid homomorphisms distribute over non-empty big ops.

separation logicprogram logicsemantics

Source project: Iris-Lean

Person-level attribution pending.

View proof record