library colibrilib.models — module NodeHModelbdd.NodeH: maps with finitely many non–empty lists
module NodeHModel1154use int.Int1155use set.Set1156use set.Cardinal1157use map.Map1158use list.List1159use list.Length1160use option.Option1161use mach.int.Int631162use colibrilib.bdd.Node1163clone SetFacts as SF {… begin (* cloned colibrilib.models.SetFacts *) let ghost SF.inter_union (t -> bool) (t -> bool) (t -> bool) (t -> bool) (t -> bool) : unit let ghost SF.card_remove t (t -> bool) : unit end } with type a = Node.t1164Valid (23ms) (colibri2)1165type t 'a = {1166ghost mutable contents: Node.t -> list 'a;1167ghost mutable keys: set Node.t;1168mutable adds: int; (* a concrete effect for add_cons *)1169} invariant { is_finite keys }1170invariant { forall k. contents k <> Nil -> mem k keys }1171by { contents = (fun _ -> Nil); keys = Set.empty; adds = 0 }1172Valid (29ms) (colibri2)1173let create (_n: int63) : t 'a1174ensures { forall k. result.contents k = Nil }1175= { contents = (fun _ -> Nil); keys = Set.empty; adds = 0 }1176Valid (97ms) (cvc5)1177let add_cons (h: t 'a) (n: Node.t) (x: 'a) : unit1178writes { h }1179ensures { h.contents = Map.set (old h.contents) n (Cons x (old h.contents n)) }1180= h.contents <- pure { Map.set h.contents n (Cons x (h.contents n)) };1181h.keys <- pure { Set.add n h.keys };1182h.adds <- h.adds + 11183
A key of s with the shortest non–empty list
Valid (1.3s) (colibri2)let rec ghost argmin (h: t 'a) (s: set Node.t) : option Node.t1186requires { is_finite s }1187ensures { match result with1188| None -> forall k. mem k s -> h.contents k = Nil1189| Some n -> mem n s /\ h.contents n <> Nil /\1190(forall k. mem k s -> h.contents k <> Nil ->1191length (h.contents n) <= length (h.contents k))1192end }1193variant { cardinal s }1194= if pure { is_empty s } then None1195else begin1196let k = pick s in1197assert { mem k s };1198SF.card_remove k s;1199let r = argmin h (remove k s) in1200match r with1201| None -> if pure { h.contents k = Nil } then None else Some k1202| Some n ->1203if pure { h.contents k <> Nil /\ length (h.contents k) < length (h.contents n) }1204then Some k else Some n1205end1206end1207Valid (397ms) (cvc5)1208let fold_min (h: t 'a) : option (Node.t, int, list 'a)1209ensures { match result with1210| None -> forall k. h.contents k = Nil1211| Some (n, len, l) -> l = h.contents n /\ l <> Nil /\ len = length l /\1212(forall k. h.contents k <> Nil -> len <= length (h.contents k))1213end }1214= let ghost w = match argmin h h.keys with1215| None -> None1216| Some n -> Some (n, length (h.contents n), h.contents n)1217end in1218any option (Node.t, int, list 'a) ensures { result = w }12191220clone colibrilib.bdd.NodeH {… begin (* cloned colibrilib.bdd.NodeH *) end } with1221type t'a = t 'a, val create = create, val add_cons = add_cons,1222val fold_min = fold_min1223end1224