List.v 1.53 KB
Newer Older
1 2 3
(********************************************************************)
(*                                                                  *)
(*  The Why3 Verification Platform   /   The Why3 Development Team  *)
Guillaume Melquiond's avatar
Guillaume Melquiond committed
4
(*  Copyright 2010-2018   --   Inria - CNRS - Paris-Sud University  *)
5 6 7 8 9 10 11
(*                                                                  *)
(*  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.                           *)
(*                                                                  *)
(********************************************************************)

12 13 14 15
(* This file is generated by Why3's Coq-realize driver *)
(* Beware! Only edit allowed sections below    *)
Require Import BuiltIn.
Require BuiltIn.
16

17
(* Why3 assumption *)
18
Definition is_nil {a:Type} {a_WT:WhyType a} (l:(list a)) : Prop :=
19 20 21 22 23 24
  match l with
  | Init.Datatypes.nil => True
  | (Init.Datatypes.cons _ _) => False
  end.

(* Why3 goal *)
25 26
Lemma is_nil_spec {a:Type} {a_WT:WhyType a} :
  forall (l:(list a)), (is_nil l) <-> (l = Init.Datatypes.nil).
27
Proof.
28
intros l.
29 30 31 32 33
split.
now destruct l.
now intros ->.
Qed.

34
Global Instance list_WhyType : forall T {T_WT : WhyType T}, WhyType (list T).
35
Proof.
36 37 38 39 40 41 42 43 44 45 46 47 48 49
split.
apply nil.
induction x as [|xh x] ; intros [|yh y] ; try (now right).
now left.
destruct (IHx y) as [->|E].
destruct (why_decidable_eq xh yh) as [->|Eh].
now left.
right.
contradict Eh.
now injection Eh.
right.
contradict E.
now injection E.
Qed.