Common — library smtlib-low-level-theory.theory — module DSeqImpl
304
module DSeqImpl : DSeq
305
306
307
use int.Int
308
use int.MinMax
309
use import map.Map as Map
310
No proof
311
type
seq
'a = {
312
length
: int;
313
default
: 'a;
314
map
: int -> 'a;
315
} invariant {
316
length >= 0 /\
317
forall i:int. not (0 <= i < length) -> map i = default
318
} by let v = any 'a in { length = 0; default = v; map = (fun _ -> v) }

Will be in Why3?

321
val ghost
record_injectivity
(x y:seq 'a) : unit
322
requires { x.length = y.length }
323
requires { x.default = y.default }
324
requires { x.map = y.map }
325
ensures { x = y }
326
No proof
327
let lemma
ext
(x:seq 'a) (y:seq 'a)
328
requires { x.length = y.length }
329
requires { x.default = y.default }
330
requires { (forall i:int. 0 <= i /\ i < x.length -> x.map i = y.map i) }
331
ensures { x = y } = record_injectivity x y
332
333
334
function
get
(x:seq 'a) (i:int) : 'a = if 0 <= i < x.length then x.map i else x.default No proof
335
let function
const
(len:int) (x:'a) : seq 'a = { length = max 0 len; default = x; map = (fun _ -> x)} No proof
336
let ghost function
set
(x:seq 'a) (i:int) (a:'a) : seq 'a =
337
if 0 <= i < x.length then
338
{ length = x.length; default=x.default; map = Map.set x.map i a }
339
else
340
x
341
No proof
342
let ghost function
extract
(x:seq 'a) (pos len:int) : seq 'a =
343
{ length = max 0 len; default=x.default; map = (fun i -> if 0 <= i < len then x.map (i+pos) else x.default ) }
344
No proof
345
let ghost function
update
(dst:seq 'a) (pos len:int) (src:seq 'a) : seq 'a =
346
{ 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 ) }
347
No proof
348
let ghost function
from_array
(len:int) (def:'a) (m:int -> 'a) : seq 'a =
349
{ length = max 0 len; default = def; map = (fun i -> if 0 <= i < len then m i else def ) }
350
No proof
351
let ghost function
rev
(s:seq 'a) : seq 'a =
352
{ length = length s; default = default s; map = (fun i -> (map s) (length s -1 - i)) }
353
354
end