def ba.lb.body

bend-osdev-algo@0.1.0.0 · PROOF.bend:1430

import Base
import bend-osdev-algo@0.1.0.0/bsearch.bend as S
import bend-osdev-array@0.1.0.0/array.bend as AR
import bend-osdev-array@0.1.0.0/LAWS.bend as AL
import bend-osdev-algo@0.1.0.0/proof_bsearch.bend as Q

1430def ba.lb.body(+d: Nat, -a: Array<U32>, +hd: {Nat.is_lt(d, 32n) == True{} : Bool}, +n: U32, +hn: {Nat.is_le(U32.to_nat(n), AR.Arrays.slots(d)) == True{} : Bool}, +key: U32, hs: {S.bsearch.sorted(List.take(&2, U32, AR.Arrays.leaves(U32, a), U32.to_nat(n))) == True{} : Bool}, +l: List<&2, U32>, +e1: {AR.Arrays.of_list(U32, d, l, 0) == a : Array<U32>}, +hl: {List.length(&2, U32, l) == AR.Arrays.slots(d) : Nat}) -> {U32.to_nat(Pair.snd(Array<U32>, U32, S.bsearch.array_lower_bound(a, n, key))) == S.bsearch.lower_bound(List.take(&2, U32, AR.Arrays.leaves(U32, a), U32.to_nat(n)), key) : Nat}:
1431  -ol = AR.Arrays.of_list(U32, d, l, 0)
1432  %e1 : {U32.to_nat(Pair.snd(Array<U32>, U32, S.bsearch.array_lower_bound(_, n, key))) == S.bsearch.lower_bound(List.take(&2, U32, AR.Arrays.leaves(U32, _), U32.to_nat(n)), key) : Nat}
1433  %Equal.sym(List<&2, U32>, AR.Arrays.leaves(U32, ol), l, AL.of_list_leaves(U32, d, l, 0, hl)) : {U32.to_nat(Pair.snd(Array<U32>, U32, S.bsearch.array_lower_bound(ol, n, key))) == S.bsearch.lower_bound(List.take(&2, U32, _, U32.to_nat(n)), key) : Nat}
1434  %Equal.sym(Array<U32> & U32, S.bsearch.array.go(33n, S.BsearchState{ol, 0, n}, key), (ol, Q.bq.run(33n, d, l, 0, n, key)), Q.bq.go(33n, d, l, hl, hd, 0, n, key)) : {U32.to_nat(Pair.snd(Array<U32>, U32, _)) == Q.bq.lb(l, n, key) : Nat}
1435  ba.answer(d, l, hl, key, n, hn, ba.hs(d, a, l, n, e1, hl, hs))