Nth.v 1.53 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
(* 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 option.Option.

(* Why3 goal *)
20 21
Definition nth: forall {a:Type} {a_WT:WhyType a}, Z -> (list a) ->
  (option a).
22 23 24 25 26
intros a a_WT.
exact (fix nth n l := match l with nil => None | cons h t => if Zeq_bool n Z0 then Some h else nth (n - 1)%Z t end).
Defined.

(* Why3 goal *)
27
Lemma nth_def : forall {a:Type} {a_WT:WhyType a}, forall (n:Z) (l:(list a)),
28
  match l with
Guillaume Melquiond's avatar
Guillaume Melquiond committed
29 30 31 32
  | Init.Datatypes.nil => ((nth n l) = Init.Datatypes.None)
  | (Init.Datatypes.cons x r) => ((n = 0%Z) -> ((nth n
      l) = (Init.Datatypes.Some x))) /\ ((~ (n = 0%Z)) -> ((nth n
      l) = (nth (n - 1%Z)%Z r)))
33 34 35 36 37 38 39 40 41 42 43 44 45 46 47
  end.
Proof.
intros a a_WT n l.
revert n.
induction l.
easy.
intros n.
split.
intros ->.
easy.
simpl.
generalize (Zeq_bool_if n 0).
now case Zeq_bool.
Qed.