library smtlib-low-level-theory.theory — module DSeqImplmodule DSeqImpl : DSeq304305306use int.Int307use int.MinMax308use import map.Map as Map309No proof310type seq 'a = {311length : int;312default: 'a;313map: int -> 'a;314} invariant {315length >= 0 /\316forall i:int. not (0 <= i < length) -> map i = default317} by let v = any 'a in { length = 0; default = v; map = (fun _ -> v) }318
Will be in Why3?
val ghost record_injectivity (x y:seq 'a) : unit321requires { x.length = y.length }322requires { x.default = y.default }323requires { x.map = y.map }324ensures { x = y }325No proof326let lemma ext (x:seq 'a) (y:seq 'a)327requires { x.length = y.length }328requires { x.default = y.default }329requires { (forall i:int. 0 <= i /\ i < x.length -> x.map i = y.map i) }330ensures { x = y } = record_injectivity x y331332333function get (x:seq 'a) (i:int) : 'a = if 0 <= i < x.length then x.map i else x.default No proof334let function const (len:int) (x:'a) : seq 'a = { length = max 0 len; default = x; map = (fun _ -> x)} No proof335let ghost function set (x:seq 'a) (i:int) (a:'a) : seq 'a =336if 0 <= i < x.length then337{ length = x.length; default=x.default; map = Map.set x.map i a }338else339x340No proof341let ghost function extract (x:seq 'a) (pos len:int) : seq 'a =342{ length = max 0 len; default=x.default; map = (fun i -> if 0 <= i < len then x.map (i+pos) else x.default ) }343No proof344let ghost function update (dst:seq 'a) (pos len:int) (src:seq 'a) : seq 'a =345{ length = dst.length; default=dst.default; map = (fun i -> if (max 0 pos) <= i < min (pos+len) dst.length then src.map (i-pos) else dst.map i ) }346No proof347let ghost function from_array (len:int) (def:'a) (m:int -> 'a) : seq 'a =348{ length = max 0 len; default = def; map = (fun i -> if 0 <= i < len then m i else def ) }349No proof350let ghost function rev (s:seq 'a) : seq 'a =351{ length = length s; default = default s; map = (fun i -> (map s) (length s -1 - i)) }352353end354