Append.v 2.76 KB
Newer Older
1 2 3 4 5 6 7 8 9 10
(********************************************************************)
(*                                                                  *)
(*  The Why3 Verification Platform   /   The Why3 Development Team  *)
(*  Copyright 2010-2015   --   INRIA - CNRS - Paris-Sud University  *)
(*                                                                  *)
(*  This software is distributed under the terms of the GNU Lesser  *)
(*  General Public License version 2.1, with the special exception  *)
(*  on linking described in file LICENSE.                           *)
(********************************************************************)

11 12 13 14 15 16 17 18 19 20
(* This file is generated by Why3's Coq-realize driver *)
(* Beware! Only edit allowed sections below    *)
Require Import BuiltIn.
Require BuiltIn.
Require int.Int.
Require list.List.
Require list.Length.
Require list.Mem.

(* Why3 goal *)
21
Lemma infix_plpl_def : forall {a:Type} {a_WT:WhyType a}, forall (l1:(list a))
22
  (l2:(list a)),
23
  ((Init.Datatypes.app l1 l2) = match l1 with
Guillaume Melquiond's avatar
Guillaume Melquiond committed
24
  | Init.Datatypes.nil => l2
25 26
  | (Init.Datatypes.cons x1 r1) =>
      (Init.Datatypes.cons x1 (Init.Datatypes.app r1 l2))
27 28
  end).
Proof.
29
now intros a a_WT [|h1 q1] l2.
30 31 32 33 34 35 36
Qed.

Require Import Lists.List.

(* Why3 goal *)
Lemma Append_assoc : forall {a:Type} {a_WT:WhyType a}, forall (l1:(list a))
  (l2:(list a)) (l3:(list a)),
37
  ((Init.Datatypes.app l1 (Init.Datatypes.app l2 l3)) = (Init.Datatypes.app (Init.Datatypes.app l1 l2) l3)).
38 39 40 41 42 43 44
Proof.
intros a a_WT l1 l2 l3.
apply app_assoc.
Qed.

(* Why3 goal *)
Lemma Append_l_nil : forall {a:Type} {a_WT:WhyType a}, forall (l:(list a)),
45
  ((Init.Datatypes.app l Init.Datatypes.nil) = l).
46 47 48 49 50 51 52 53
Proof.
intros a a_WT l.
apply app_nil_r.
Qed.

(* Why3 goal *)
Lemma Append_length : forall {a:Type} {a_WT:WhyType a}, forall (l1:(list a))
  (l2:(list a)),
54
  ((list.Length.length (Init.Datatypes.app l1 l2)) = ((list.Length.length l1) + (list.Length.length l2))%Z).
55 56 57 58 59 60 61 62
Proof.
intros a a_WT l1 l2.
rewrite 3!Length.length_std.
now rewrite app_length, inj_plus.
Qed.

(* Why3 goal *)
Lemma mem_append : forall {a:Type} {a_WT:WhyType a}, forall (x:a)
63 64 65
  (l1:(list a)) (l2:(list a)), (list.Mem.mem x
  (Init.Datatypes.app l1 l2)) <-> ((list.Mem.mem x l1) \/ (list.Mem.mem x
  l2)).
66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89
Proof.
intros a a_WT x l1 l2.
split.
intros H.
apply Mem.mem_std in H.
apply in_app_or in H.
destruct H as [H|H].
left.
now apply Mem.mem_std.
right.
now apply Mem.mem_std.
intros H.
apply Mem.mem_std.
apply in_or_app.
destruct H as [H|H].
left.
now apply Mem.mem_std.
right.
now apply Mem.mem_std.
Qed.

(* Why3 goal *)
Lemma mem_decomp : forall {a:Type} {a_WT:WhyType a}, forall (x:a)
  (l:(list a)), (list.Mem.mem x l) -> exists l1:(list a), exists l2:(list a),
90
  (l = (Init.Datatypes.app l1 (Init.Datatypes.cons x l2))).
91 92 93 94 95 96
Proof.
intros a a_WT x l h1.
apply in_split.
now apply Mem.mem_std.
Qed.