library colibrilib.fp_interval — module Intervalsmodule Intervals9use list.List10use list.Length11use int.Int12use colibrilib.fbin.Fp13use colibrilib.fp_facts.Facts14
The floats of [a, b]
predicate in_iv (v: t) (a b: t) = le_dz a v /\ le_dz v b1718predicate mem_u (v: t) (l: list (t, t)) =19match l with20| Nil -> false21| Cons (a, b) r -> in_iv v a b \/ mem_u v r22end23
Sorted, disjoint, not NaN, not empty
predicate ok_u (l: list (t, t)) =26match l with27| Nil -> true28| Cons (a, b) r ->29is_not_nan a /\ is_not_nan b /\ le_dz a b /\30(match r with Nil -> true | Cons (a', _) _ -> lt_dz b a' end) /\31ok_u r32end33
The bounds of l are floats of the format fm
predicate fmt_u (fm: format) (l: list (t, t)) =36match l with37| Nil -> true38| Cons (a, b) r -> fmt a = fm /\ fmt b = fm /\ fmt_u fm r39end40
Every float of l is above x
predicate above (x: t) (l: list (t, t)) = forall v. mem_u v l -> lt_dz x v43Valid (24ms) (colibri2)44let rec ghost sorted_above (b: t) (l: list (t, t)) : unit45requires { ok_u l }46requires { match l with Nil -> true | Cons (a, _) _ -> lt_dz b a end }47ensures { above b l }48variant { l }49= {proof…} match l with50| Nil -> ()51| Cons (a, b') r ->52lt_le_trans_any b a b'; lt_le_any b b';53(match r with Nil -> () | Cons _ _ -> sorted_above b' r end);54let lemma pt (v: t) : unit55requires { mem_u v l }56ensures { lt_dz b v }57= lt_le_trans_any b a v; le_lt_trans_any b b' v in58()59end {qed}60
The floats of a list are not NaN, and of the format of its bounds
Valid (11ms) (colibri2)let rec ghost mem_u_not_nan (v: t) (l: list (t, t)) : unit63requires { mem_u v l }64ensures { is_not_nan v }65ensures { forall fm. fmt_u fm l -> fmt v = fm }66variant { l }67= {proof…} match l with68| Nil -> ()69| Cons (a, b) r -> if pure { in_iv v a b } then () else mem_u_not_nan v r70end {qed}71
The first float of a list is in it
Valid (10ms) (colibri2)let ghost head_mem (l: list (t, t)) : unit74requires { ok_u l }75ensures { match l with Nil -> true | Cons (a, _) _ -> mem_u a l end }76= {proof…} match l with77| Nil -> ()78| Cons (a, _) _ -> le_refl_any a79end {qed}80
A list above x starts above x
Valid (14ms) (colibri2)let ghost above_head (x: t) (l: list (t, t)) : unit83requires { ok_u l /\ above x l }84ensures { match l with Nil -> true | Cons (a, _) _ -> lt_dz x a end }85= {proof…} head_mem l {qed}86
Two overlapping intervals, the first starting first: their union is [a1, max b1 b2]
Valid (63ms) (cvc4)let ghost merge (a1 b1 a2 b2: t) : unit90requires { le_dz a1 a2 /\ le_dz a2 b2 /\ le_dz a1 b1 /\ not (lt_dz b1 a2) }91ensures { le_dz b1 b2 -> forall v. in_iv v a1 b2 <-> in_iv v a1 b1 \/ in_iv v a2 b2 }92ensures { not (le_dz b1 b2) -> forall v. in_iv v a1 b1 <-> in_iv v a1 b1 \/ in_iv v a2 b2 }93= {proof…}94le_not_nan_any a1 b1; le_not_nan_any a2 b2; total_any b1 b2; total_any b1 a2;95let lemma pt (v: t) : unit96ensures { le_dz b1 b2 -> (in_iv v a1 b2 <-> in_iv v a1 b1 \/ in_iv v a2 b2) }97ensures { not (le_dz b1 b2) -> (in_iv v a1 b1 <-> in_iv v a1 b1 \/ in_iv v a2 b2) }98= le_trans_any v b1 b2; le_trans_any a1 a2 v; lt_le_any b2 b1; le_trans_any v b2 b1;99le_not_nan_any a1 v; total_any v b1; total_any a2 v; lt_le_any b1 v; le_lt_trans_any b1 v a2 in100() {qed}101
The union of two lists
Valid (896ms) (colibri2 27) (cvc4) (cvc5 2) (split_vc 3) (depth 3)let rec union_u (ghost fm: format) (l1 l2: list (t, t)) : list (t, t)104requires { ok_u l1 /\ ok_u l2 /\ fmt_u fm l1 /\ fmt_u fm l2 }105ensures { ok_u result /\ fmt_u fm result }106ensures { forall v. mem_u v result <-> mem_u v l1 \/ mem_u v l2 }107variant { length l1 + length l2 }108= match l1, l2 with109| Nil, l | l, Nil -> l110| Cons (a1, b1) d1, Cons (a2, b2) d2 ->111if lt_diff_zero b1 a2 then begin112let r = union_u fm d1 l2 in113{proof…} (match d1 with Nil -> () | Cons _ _ -> sorted_above b1 d1 end);114sorted_above b1 l2; above_head b1 r; {qed}115Cons (a1, b1) r116end else if lt_diff_zero b2 a1 then begin117let r = union_u fm l1 d2 in118{proof…} (match d2 with Nil -> () | Cons _ _ -> sorted_above b2 d2 end);119sorted_above b2 l1; above_head b2 r; {qed}120Cons (a2, b2) r121end else if le_diff_zero a1 a2 then begin122{proof…} merge a1 b1 a2 b2; {qed}123if le_diff_zero b1 b2 then begin124{proof…} le_trans_any a1 a2 b2; {qed}125union_u fm d1 (Cons (a1, b2) d2)126end else127union_u fm l1 d2128end else begin129{proof…} le_not_nan_any a1 b1; le_not_nan_any a2 b2; total_any a1 a2; lt_le_any a2 a1;130merge a2 b2 a1 b1; {qed}131if le_diff_zero b2 b1 then begin132{proof…} le_trans_any a2 a1 b1; {qed}133union_u fm (Cons (a2, b1) d1) d2134end else135union_u fm d1 l2136end137end138
The intersection of two lists
Valid (1.2s) (colibri2 22) (cvc5 5) (split_vc) (depth 1)let rec inter_u (ghost fm: format) (l1 l2: list (t, t)) : list (t, t)141requires { ok_u l1 /\ ok_u l2 /\ fmt_u fm l1 /\ fmt_u fm l2 }142ensures { ok_u result /\ fmt_u fm result }143ensures { forall v. mem_u v result <-> mem_u v l1 /\ mem_u v l2 }144variant { length l1 + length l2 }145= match l1, l2 with146| Nil, _ | _, Nil -> Nil147| Cons (a1, b1) d1, Cons (a2, b2) d2 ->148{proof…} le_not_nan_any a1 b1; le_not_nan_any a2 b2;149(match d1 with Nil -> () | Cons _ _ -> sorted_above b1 d1 end);150(match d2 with Nil -> () | Cons _ _ -> sorted_above b2 d2 end); {qed}151if lt_diff_zero b1 a2 then begin152{proof…} sorted_above b1 l2;153let lemma pt (v: t) : unit154ensures { in_iv v a1 b1 -> not (mem_u v l2) }155= lt_not_le_any b1 v in {qed}156inter_u fm d1 l2157end else if lt_diff_zero b2 a1 then begin158{proof…} sorted_above b2 l1;159let lemma pt (v: t) : unit160ensures { in_iv v a2 b2 -> not (mem_u v l1) }161= lt_not_le_any b2 v in {qed}162inter_u fm l1 d2163end else begin164let a = max_diff_zero a1 a2 in165{proof…} total_any b1 a2; total_any b2 a1; total_any b1 b2; {qed}166if le_diff_zero b2 b1 then begin167(* without `succ`: [a1, b1] stays whole, the next intervals of l2 start above b2 *)169let r = inter_u fm l1 d2 in170{proof…} above_head b2 r;171le_trans_any a1 a2 b2; le_trans_any a2 a1 b2;172let lemma pt (v: t) : unit173ensures { in_iv v a b2 <-> in_iv v a1 b1 /\ in_iv v a2 b2 }174= le_trans_any a1 a v; le_trans_any a2 a v; le_trans_any v b2 b1;175le_not_nan_any a1 v; total_any a1 a2; lt_le_any a2 a1 in176let lemma below (v: t) : unit177ensures { in_iv v a1 b1 /\ mem_u v d2 -> not (in_iv v a2 b2) }178= lt_not_le_any b2 v in {qed}179Cons (a, b2) r180end else begin181let r = inter_u fm d1 l2 in182{proof…} above_head b1 r; lt_le_any b1 b2;183le_trans_any a1 a2 b1; le_trans_any a2 a1 b1;184let lemma pt (v: t) : unit185ensures { in_iv v a b1 <-> in_iv v a1 b1 /\ in_iv v a2 b2 }186= le_trans_any a1 a v; le_trans_any a2 a v; le_trans_any v b1 b2;187le_not_nan_any a1 v; total_any a1 a2; lt_le_any a2 a1 in188let lemma below (v: t) : unit189ensures { in_iv v a2 b2 /\ mem_u v d1 -> not (in_iv v a1 b1) }190= lt_not_le_any b1 v in {qed}191Cons (a, b1) r192end193end194end195
No float in both lists
Valid (458ms) (colibri2 11) (cvc5 2) (split_vc) (depth 1)let rec is_distinct_u (ghost fm: format) (l1 l2: list (t, t)) : bool198requires { ok_u l1 /\ ok_u l2 /\ fmt_u fm l1 /\ fmt_u fm l2 }199ensures { result <-> forall v. not (mem_u v l1 /\ mem_u v l2) }200variant { length l1 + length l2 }201= match l1, l2 with202| Nil, _ | _, Nil -> true203| Cons (a1, b1) d1, Cons (a2, b2) d2 ->204if lt_diff_zero b1 a2 then begin205{proof…} sorted_above b1 l2;206let lemma pt (v: t) : unit207ensures { in_iv v a1 b1 -> not (mem_u v l2) }208= lt_not_le_any b1 v in {qed}209is_distinct_u fm d1 l2210end else if lt_diff_zero b2 a1 then begin211{proof…} sorted_above b2 l1;212let lemma pt (v: t) : unit213ensures { in_iv v a2 b2 -> not (mem_u v l1) }214= lt_not_le_any b2 v in {qed}215is_distinct_u fm l1 d2216end else begin217{proof…} le_not_nan_any a1 b1; le_not_nan_any a2 b2;218let ghost a = max_diff_zero a1 a2 in219total_any b1 a2; total_any b2 a1; le_refl_any a;220le_trans_any a a1 b1; le_trans_any a a2 b2;221assert { in_iv a a1 b1 /\ in_iv a a2 b2 }; {qed}222false223end224end225226predicate incl_u (l1 l2: list (t, t)) = forall v. mem_u v l1 -> mem_u v l2227
Inclusion. When the interval of l1 goes beyond the one of l2, the rest of it starts at the successor: the next interval of l2 may start there (adjacent intervals).
Valid (559ms) (colibri2 59) (cvc4 4) (cvc5 6) (split_vc 8) (depth 4)let rec is_included_u (ghost fm: format) (l1 l2: list (t, t)) : bool232requires { ok_u l1 /\ ok_u l2 /\ fmt_u fm l1 /\ fmt_u fm l2 }233ensures { result <-> incl_u l1 l2 }234variant { length l1 + length l2 }235= match l1, l2 with236| Nil, _ -> true237| Cons _ _, Nil ->238{proof…} head_mem l1; assert { not incl_u l1 l2 }; {qed} false239| Cons (a1, b1) d1, Cons (a2, b2) d2 ->240{proof…} head_mem l1; le_not_nan_any a1 b1; le_not_nan_any a2 b2; {qed}241if lt_diff_zero b1 a2 then begin242{proof…} sorted_above b1 l2; lt_not_le_any b1 a1;243assert { not incl_u l1 l2 }; {qed}244false245end else if lt_diff_zero b2 a1 then begin246{proof…} sorted_above b2 l1;247let lemma pt (v: t) : unit248ensures { mem_u v l1 -> not (in_iv v a2 b2) }249= lt_not_le_any b2 v in250assert { incl_u l1 l2 <-> incl_u l1 d2 }; {qed}251is_included_u fm l1 d2252end else if le_diff_zero b2 b1 then begin253{proof…}254(match d2 with Nil -> () | Cons _ _ -> sorted_above b2 d2 end);255{qed}256if not (le_diff_zero a2 a1) then begin257{proof…} total a2 a1; lt_le_trans_any a1 a2 b2;258lt_not_le_any a1 a2;259assert { not (mem_u a1 d2) by forall v. mem_u v d2 -> lt_dz b2 v };260assert { not incl_u l1 l2 }; {qed}261false262end else if le_diff_zero b1 b2 then begin263{proof…}264(match d1 with Nil -> () | Cons _ _ -> sorted_above b1 d1 end);265let lemma pt (v: t) : unit266ensures { mem_u v d1 -> not (in_iv v a2 b2) /\ not (in_iv v a1 b1) }267= lt_not_le_any b1 v in268let lemma pt2 (v: t) : unit269ensures { in_iv v a1 b1 -> in_iv v a2 b2 }270= le_trans_any a2 a1 v; le_trans_any v b1 b2 in271let lemma dir1 (v: t) : unit272requires { incl_u l1 l2 /\ mem_u v d1 } ensures { mem_u v d2 }273= assert { mem_u v l1 } in274let lemma dir2 (v: t) : unit275requires { incl_u d1 d2 /\ mem_u v l1 } ensures { mem_u v l2 }276= () in277assert { incl_u l1 l2 <-> incl_u d1 d2 }; {qed}278is_included_u fm d1 d2279end else begin280{proof…}281total b1 b2; succ_gt b2; succ_least b2 b1;282let ghost s = succ_dz b2 in283(match d1 with Nil -> () | Cons _ _ -> sorted_above b1 d1 end);284let lemma pt (v: t) : unit285ensures { mem_u v d1 -> not (in_iv v a2 b2) /\ lt_dz b1 v }286= lt_not_le_any b1 v; le_lt_trans_any v b2 b1 in287let lemma pt_up (v: t) : unit288ensures { in_iv v s b1 -> in_iv v a1 b1 /\ not (in_iv v a2 b2) }289= lt_le_trans_any b2 s v; lt_not_le_any b2 v;290le_trans_any a1 b2 v; lt_le_any b2 v; total_any a1 b2 in291let lemma pt_split (v: t) : unit292ensures { in_iv v a1 b1 -> in_iv v a2 b2 \/ in_iv v s b1 }293= le_trans_any a2 a1 v; le_not_nan_any a1 v; total_any v b2;294if pure { in_iv v a1 b1 /\ lt_dz b2 v } then succ_least b2 v in295let lemma dir1 (v: t) : unit296requires { incl_u l1 l2 /\ mem_u v (Cons (s, b1) d1) }297ensures { mem_u v d2 }298= assert { mem_u v l1 /\ not (in_iv v a2 b2) } in299let lemma dir2 (v: t) : unit300requires { incl_u (Cons (s, b1) d1) d2 /\ mem_u v l1 }301ensures { mem_u v l2 }302= if pure { in_iv v a1 b1 } then begin303if pure { in_iv v s b1 } then assert { mem_u v d2 }304end else assert { mem_u v d2 } in305assert { incl_u l1 l2 <-> incl_u (Cons (s, b1) d1) d2 }; {qed}306is_included_u fm (Cons (succ_diff_zero b2, b1) d1) d2307end308end else begin309{proof…} total b2 b1; total a2 a1;310(match d1 with Nil -> () | Cons _ _ -> sorted_above b1 d1 end);311(match d2 with Nil -> () | Cons _ _ -> sorted_above b2 d2 end);312let lemma not_first () : unit313requires { not (le_dz a2 a1) } ensures { not (mem_u a1 l2) }314= lt_not_le_any a1 a2; lt_le_trans_any a1 a2 b2;315assert { forall v. mem_u v d2 -> lt_dz b2 v } in316let lemma dir1 (v: t) : unit317requires { incl_u l1 l2 /\ mem_u v d1 } ensures { mem_u v l2 }318= assert { mem_u v l1 } in319let lemma dir2 (v: t) : unit320requires { le_dz a2 a1 /\ incl_u d1 l2 /\ mem_u v l1 }321ensures { mem_u v l2 }322= () in323let lemma pt (v: t) : unit324ensures { in_iv v a1 b1 -> le_dz a2 a1 -> in_iv v a2 b2 }325= le_trans_any a2 a1 v; lt_le_any b1 b2; le_trans_any v b1 b2 in326assert { not (le_dz a2 a1) -> not incl_u l1 l2 };327assert { le_dz a2 a1 -> (incl_u l1 l2 <-> incl_u d1 l2) }; {qed}328le_diff_zero a2 a1 && is_included_u fm d1 l2329end330end331332predicate diff_spec (r l1 l2: list (t, t)) =333forall v. mem_u v r <-> mem_u v l1 /\ not mem_u v l2334
A list included in l is above everything l is above
Valid (26ms) (colibri2)let ghost sub_above (x: t) (r l: list (t, t)) : unit337requires { ok_u r /\ above x l /\ forall v. mem_u v r -> mem_u v l }338ensures { match r with Nil -> true | Cons (a, _) _ -> lt_dz x a end }339= {proof…} head_mem r {qed}340
The difference. The parts of l1 that remain end at the predecessor of an interval of l2, or start at the successor of its end.
Valid (1.4s) (colibri2 62) (cvc4) (cvc5 11) (split_vc 11) (depth 5)let rec diff_u (ghost fm: format) (l1 l2: list (t, t)) : list (t, t)344requires { ok_u l1 /\ ok_u l2 /\ fmt_u fm l1 /\ fmt_u fm l2 }345ensures { ok_u result /\ fmt_u fm result /\ diff_spec result l1 l2 }346variant { length l1 + length l2 }347= match l1, l2 with348| Nil, _ -> Nil349| Cons _ _, Nil -> l1350| Cons (a1, b1) d1, Cons (a2, b2) d2 ->351{proof…} le_not_nan_any a1 b1; le_not_nan_any a2 b2;352(match d1 with Nil -> () | Cons _ _ -> sorted_above b1 d1 end);353(match d2 with Nil -> () | Cons _ _ -> sorted_above b2 d2 end);354{qed}355if lt_diff_zero b1 a2 then begin356let r = diff_u fm d1 l2 in357{proof…} sorted_above b1 l2; sub_above b1 r d1;358let lemma pt (v: t) : unit359ensures { in_iv v a1 b1 -> not (mem_u v l2) }360= lt_not_le_any b1 v in361let lemma pt2 (v: t) : unit362ensures { mem_u v d1 -> not (in_iv v a1 b1) }363= lt_not_le_any b1 v in364assert { diff_spec (Cons (a1, b1) r) l1 l2 }; {qed}365Cons (a1, b1) r366end else if lt_diff_zero b2 a1 then begin367{proof…} sorted_above b2 l1;368let lemma pt (v: t) : unit369ensures { mem_u v l1 -> not (in_iv v a2 b2) }370= lt_not_le_any b2 v in {qed}371diff_u fm l1 d2372end else begin373let r =374if le_diff_zero b2 b1 then begin375if le_diff_zero b1 b2 then begin376let r = diff_u fm d1 d2 in377{proof…}378let lemma pt (v: t) : unit379ensures { mem_u v d1 -> not (in_iv v a2 b2) /\ not (in_iv v a1 b1) }380= lt_not_le_any b1 v in381let lemma pt2 (v: t) : unit382ensures { mem_u v d2 -> not (in_iv v a1 b1) }383= lt_not_le_any b2 v in384assert { forall v. mem_u v r ->385mem_u v l1 /\ not mem_u v l2 /\ lt_dz b2 v };386assert { forall v. mem_u v l1 /\ not mem_u v l2 ->387(lt_dz v a2 \/ mem_u v r) };388{qed}389r390end else begin391{proof…} total b1 b2; succ_gt b2; succ_least b2 b1; {qed}392let l1' = Cons (succ_diff_zero b2, b1) d1 in393let r = diff_u fm l1' d2 in394{proof…}395let ghost s = succ_dz b2 in396let lemma pt (v: t) : unit397ensures { mem_u v d1 -> not (in_iv v a2 b2) /\ lt_dz b1 v }398= lt_not_le_any b1 v; le_lt_trans_any v b2 b1 in399let lemma pt_up (v: t) : unit400ensures { in_iv v s b1 -> in_iv v a1 b1 /\ not (in_iv v a2 b2) /\ lt_dz b2 v }401= lt_le_trans_any b2 s v; lt_not_le_any b2 v;402le_trans_any a1 b2 v; lt_le_any b2 v; total_any a1 b2 in403let lemma pt_split (v: t) : unit404ensures { in_iv v a1 b1 -> lt_dz v a2 \/ in_iv v a2 b2 \/ in_iv v s b1 }405= le_not_nan_any a1 v; total_any v b2; total_any a2 v;406if pure { in_iv v a1 b1 /\ lt_dz b2 v } then succ_least b2 v in407let lemma pt2 (v: t) : unit408ensures { mem_u v d2 -> lt_dz b2 v }409= () in410assert { forall v. mem_u v r ->411mem_u v l1 /\ not mem_u v l2 /\ lt_dz b2 v };412assert { forall v. mem_u v l1 /\ not mem_u v l2 ->413(lt_dz v a2 \/ mem_u v r) };414{qed}415r416end417end else begin418let r = diff_u fm d1 l2 in419{proof…} total b2 b1;420let lemma pt (v: t) : unit421ensures { mem_u v d1 -> lt_dz b1 v }422= () in423let lemma pt2 (v: t) : unit424ensures { in_iv v a1 b1 -> not (mem_u v d2) }425= lt_le_any b1 b2; le_lt_trans_any v b1 b2;426assert { forall w. mem_u w d2 -> lt_dz b2 w };427lt_not_le_any v b2 in428let lemma pt3 (v: t) : unit429ensures { in_iv v a1 b1 -> not (in_iv v a2 b2) -> lt_dz v a2 }430= le_not_nan_any a1 v; total_any a2 v; lt_le_any b1 b2;431le_trans_any v b1 b2 in432assert { forall v. mem_u v r ->433mem_u v l1 /\ not mem_u v l2 /\ lt_dz b1 v };434assert { forall v. mem_u v l1 /\ not mem_u v l2 ->435(lt_dz v a2 \/ mem_u v r) };436{qed}437r438end in439{proof…}440assert { forall v. mem_u v r -> lt_dz a2 v441by lt_dz b1 v \/ lt_dz b2 v };442{qed}443if lt_diff_zero a1 a2 then begin444{proof…}445pred_lt a2; pred_greatest a2 a1;446let ghost p = pred_dz a2 in447let lemma pt (v: t) : unit448requires { in_iv v a1 p }449ensures { mem_u v l1 /\ not mem_u v l2 /\ lt_dz v a2 }450= le_lt_trans v p a2; lt_not_le v a2;451lt_le_trans v a2 b2; lt_not_le v b2;452assert { not (mem_u v d2) by forall w. mem_u w d2 -> lt_dz b2 w453so (forall w. lt_dz b2 w -> w <> v) };454total_any v b1 in455let lemma pt2 (v: t) : unit456requires { mem_u v l1 /\ lt_dz v a2 }457ensures { in_iv v a1 p }458= pred_greatest a2 v; total_any b1 a2;459assert { not (mem_u v d1) by forall w. mem_u w d1 -> lt_dz b1 w };460lt_le_any v a2 in461assert { forall v. mem_u v r -> lt_dz p v by lt_dz p a2 /\ lt_dz a2 v };462(match r with Nil -> () | Cons _ _ -> head_mem r end);463{qed}464Cons (a1, pred_diff_zero a2) r465end else begin466{proof…} total a2 a1;467let lemma pt (v: t) : unit468ensures { mem_u v l1 -> not (lt_dz v a2) }469= assert { forall w. mem_u w d1 -> lt_dz b1 w };470le_trans_any a2 a1 v; lt_not_le_any v a2 in471{qed}472r473end474end475end476477predicate disj_u (l1 l2: list (t, t)) = forall v. not (mem_u v l1 /\ mem_u v l2)478479type comparison = Uncomparable | Included | Disjoint480
Included, disjoint or neither, for a non–empty l1
Valid (590ms) (colibri2 16) (cvc4 2) (cvc5 5) (split_vc) (depth 1)let rec is_distinct_or_included_u (ghost fm: format) (l1 l2: list (t, t)) : comparison483requires { ok_u l1 /\ ok_u l2 /\ fmt_u fm l1 /\ fmt_u fm l2 /\ l1 <> Nil }484ensures { result = Included <-> incl_u l1 l2 }485ensures { result = Disjoint <-> disj_u l1 l2 }486variant { l2 }487= match l1, l2 with488| Nil, _ -> absurd489| Cons _ _, Nil -> {proof…} head_mem l1; {qed} Disjoint490| Cons (a1, b1) d1, Cons (a2, b2) d2 ->491{proof…} head_mem l1; le_not_nan_any a1 b1; le_not_nan_any a2 b2; {qed}492if lt_diff_zero b1 a2 then begin493{proof…} sorted_above b1 l2; lt_not_le_any b1 a1;494let lemma pt (v: t) : unit495ensures { in_iv v a1 b1 -> not (mem_u v l2) }496= lt_not_le_any b1 v in497assert { not incl_u l1 l2 };498assert { disj_u l1 l2 <-> disj_u d1 l2 }; {qed}499if is_distinct_u fm d1 l2 then Disjoint else Uncomparable500end else if lt_diff_zero b2 a1 then begin501{proof…} sorted_above b2 l1;502let lemma pt (v: t) : unit503ensures { mem_u v l1 -> not (in_iv v a2 b2) }504= lt_not_le_any b2 v in505assert { incl_u l1 l2 <-> incl_u l1 d2 };506assert { disj_u l1 l2 <-> disj_u l1 d2 }; {qed}507is_distinct_or_included_u fm l1 d2508end else begin509{proof…}510let ghost a = max_diff_zero a1 a2 in511total_any b1 a2; total_any b2 a1; le_refl_any a;512le_trans_any a a1 b1; le_trans_any a a2 b2;513assert { in_iv a a1 b1 /\ in_iv a a2 b2 };514assert { not disj_u l1 l2 }; {qed}515if is_included_u fm l1 l2 then Included else Uncomparable516end517end518end519