vstte12_tree_reconstruction_Harness_VC_harness_1.v 2.7 KB
Newer Older
1 2
(* This file is generated by Why3's Coq driver *)
(* Beware! Only edit allowed sections below    *)
3 4
Require Import BuiltIn.
Require BuiltIn.
5
Require int.Int.
6 7 8 9
Require list.List.
Require list.Length.
Require list.Mem.
Require list.Append.
10

11
(* Why3 assumption *)
12 13 14
Inductive tree :=
  | Leaf : tree
  | Node : tree -> tree -> tree.
15 16
Axiom tree_WhyType : WhyType tree.
Existing Instance tree_WhyType.
17

18
(* Why3 assumption *)
19
Fixpoint depths (d:Z) (t:tree) {struct t}: (list Z) :=
20
  match t with
21
  | Leaf => (Init.Datatypes.cons d Init.Datatypes.nil)
22 23
  | Node l r =>
      (Init.Datatypes.app (depths (d + 1%Z)%Z l) (depths (d + 1%Z)%Z r))
24 25
  end.

26 27 28
Axiom depths_head :
  forall (t:tree) (d:Z),
  match depths d t with
29 30
  | (Init.Datatypes.cons x _) => (d <= x)%Z
  | Init.Datatypes.nil => False
31 32
  end.

33 34 35 36 37
Axiom depths_unique :
  forall (t1:tree) (t2:tree) (d:Z) (s1:(list Z)) (s2:(list Z)),
  ((Init.Datatypes.app (depths d t1) s1) =
   (Init.Datatypes.app (depths d t2) s2)) ->
  (t1 = t2) /\ (s1 = s2).
38

39 40 41 42 43
Axiom depths_prefix :
  forall (t:tree) (d1:Z) (d2:Z) (s1:(list Z)) (s2:(list Z)),
  ((Init.Datatypes.app (depths d1 t) s1) =
   (Init.Datatypes.app (depths d2 t) s2)) ->
  (d1 = d2).
44

45 46
Axiom depths_prefix_simple :
  forall (t:tree) (d1:Z) (d2:Z), ((depths d1 t) = (depths d2 t)) -> (d1 = d2).
47

48 49 50
Axiom depths_subtree :
  forall (t1:tree) (t2:tree) (d1:Z) (d2:Z) (s1:(list Z)),
  ((Init.Datatypes.app (depths d1 t1) s1) = (depths d2 t2)) -> (d2 <= d1)%Z.
51

52 53 54
Axiom depths_unique2 :
  forall (t1:tree) (t2:tree) (d1:Z) (d2:Z),
  ((depths d1 t1) = (depths d2 t2)) -> (d1 = d2) /\ (t1 = t2).
55 56

(* Why3 assumption *)
57
Definition lex (x1:((list Z)* Z)%type) (x2:((list Z)* Z)%type) : Prop :=
58 59 60
  match x1 with
  | (s1, d1) =>
      match x2 with
61 62 63 64 65 66 67 68
      | (s2, d2) =>
          ((list.Length.length s1) < (list.Length.length s2))%Z \/
          (((list.Length.length s1) = (list.Length.length s2)) /\
           match (s1, s2) with
           | ((Init.Datatypes.cons h1 _), (Init.Datatypes.cons h2 _)) =>
               (d2 < d1)%Z /\ ((d1 <= h1)%Z /\ (h1 = h2))
           | _ => False
           end)
69 70 71
      end
  end.

72
(* Why3 goal *)
73 74 75 76 77 78
Theorem VC_harness :
  forall (result:tree),
  ((depths 0%Z result) =
   (Init.Datatypes.cons 1%Z
    (Init.Datatypes.cons 3%Z
     (Init.Datatypes.cons 3%Z (Init.Datatypes.cons 2%Z Init.Datatypes.nil))))) ->
79
  (result = (Node Leaf (Node (Node Leaf Leaf) Leaf))).
80
(* Why3 intros result h1. *)
81

82 83
intuition.

84 85 86
rewrite <- (Append.Append_l_nil (depths 0 result)) in H.
rewrite <- (Append.Append_l_nil (cons 1%Z (cons 3%Z (cons 3%Z (cons 2%Z nil))))) in H.
assert (cons 1%Z (cons 3%Z (cons 3%Z (cons 2%Z nil))) = depths 0 (Node Leaf (Node (Node Leaf Leaf) Leaf))) by reflexivity.
87
rewrite H0 in H.
88 89 90 91
generalize (depths_unique _ _ _ _ _ H); intuition.

Qed.