val lemma_index_upd1' (#a: Type) (s: seq a) (n: nat{n < length s}) (v: a)
    : Lemma (requires True) (ensures (index (upd s n v) n == v)) (decreases (length s))
let rec lemma_index_upd1' (#a:Type) (s:seq a) (n:nat{n < length s}) (v:a)
  : Lemma
    (requires True)
    (ensures (index (upd s n v) n == v)) (decreases (length s))
= if n = 0
  then ()
  else begin
    lemma_index_upd1' #a (tl s) (n - 1) v;
    assert (index (upd (tl s) (n-1) v) (n-1) == v)
  end
val lemma_index_upd1' (#a: Type) (s: seq a) (n: nat{n < length s}) (v: a)
    : Lemma (requires True) (ensures (index (upd s n v) n == v)) (decreases (length s))
let rec lemma_index_upd1' (#a: Type) (s: seq a) (n: nat{n < length s}) (v: a)
    : Lemma (requires True) (ensures (index (upd s n v) n == v)) (decreases (length s)) =
if n = 0
then ()
else
  (lemma_index_upd1' #a (tl s) (n - 1) v;
    assert (index (upd (tl s) (n - 1) v) (n - 1) == v))
FStar.Seq.Base.fst.checked
prims.fst.checked FStar.Pervasives.fsti.checked FStar.List.Tot.fst.checked
FStar.Seq.Base.fst
FStar.Seq.Base.seq Prims.nat Prims.b2t Prims.op_LessThan FStar.Seq.Base.length Prims.op_Equality Prims.int Prims.bool Prims._assert Prims.eq2 FStar.Seq.Base.index FStar.Seq.Base.upd FStar.Seq.Base.tl Prims.op_Subtraction Prims.unit FStar.Seq.Base.lemma_index_upd1' Prims.l_True Prims.squash Prims.Nil FStar.Pervasives.pattern
(*
   Copyright 2008-2014 Nikhil Swamy and Microsoft Research

   Licensed under the Apache License, Version 2.0 (the "License");
   you may not use this file except in compliance with the License.
   You may obtain a copy of the License at

       http://www.apache.org/licenses/LICENSE-2.0

   Unless required by applicable law or agreed to in writing, software
   distributed under the License is distributed on an "AS IS" BASIS,
   WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
   See the License for the specific language governing permissions and
   limitations under the License.
*)

(* A logical theory of sequences indexed by natural numbers in [0, n) *)
module FStar.Seq.Base
//#set-options "--initial_fuel 0 --max_fuel 0 --initial_ifuel 1 --max_ifuel 1"

module List = FStar.List.Tot

type seq (a:Type u#a) :Type u#a =
  | MkSeq: l:list a -> seq a

let length #_ s = List.length (MkSeq?.l s)

let index #_ s i = List.index (MkSeq?.l s) i

let cons (#a:Type) (x:a) (s:seq a) : Tot (seq a) = MkSeq (x::(MkSeq?.l s))

let hd (#a:Type) (s:seq a{length s > 0}) : Tot a = List.hd (MkSeq?.l s)

let tl (#a:Type) (s:seq a{length s > 0}) : Tot (seq a) = MkSeq (List.tl (MkSeq?.l s))

let rec create #_ len v = if len = 0 then MkSeq [] else cons v (create (len - 1) v)

private let rec init_aux' (#a:Type) (len:nat) (k:nat{k < len}) (contents: (i:nat{i < len} -> Tot a))
    : Tot (seq a)
      (decreases (len - k))
  = if k + 1 = len
    then MkSeq [contents k]
    else cons (contents k) (init_aux' len (k+1) contents)

let init_aux = init_aux'

let init #_ len contents = if len = 0 then MkSeq [] else init_aux len 0 contents

private let rec init_aux_ghost' (#a:Type) (len:nat) (k:nat{k < len}) (contents:(i:nat { i < len } -> GTot a))
    : GTot (seq a)
      (decreases (len - k))
  = if k + 1 = len
    then MkSeq [contents k]
    else cons (contents k) (init_aux_ghost' len (k+1) contents)

let init_aux_ghost = init_aux_ghost'

let init_ghost #_ len contents = if len = 0 then MkSeq [] else init_aux_ghost len 0 contents

let empty #_ = MkSeq []

let lemma_empty #_ _ = ()

private let rec upd' (#a:Type) (s:seq a) (n:nat{n < length s}) (v:a)
    : Tot (seq a)
      (decreases (length s))
  = if n = 0 then cons v (tl s) else cons (hd s) (upd' (tl s) (n - 1) v)

let upd = upd'

let append #_ s1 s2 = MkSeq (List.append (MkSeq?.l s1) (MkSeq?.l s2))

private let rec slice' (#a:Type) (s:seq a) (i:nat) (j:nat{i <= j && j <= length s})
    : Tot (seq a)
      (decreases (length s))
  =  if i > 0 then slice' #a (tl s) (i - 1) (j - 1)
     else if j = 0 then MkSeq []
          else cons (hd s) (slice' #a (tl s) i (j - 1))

let slice = slice'

let rec lemma_create_len #_ n i = if n = 0 then () else lemma_create_len (n - 1) i

let rec lemma_init_aux_len' (#a:Type) (n:nat) (k:nat{k < n}) (contents:(i:nat{ i < n } -> Tot a))
  : Lemma (requires True)
    (ensures (length (init_aux n k contents) = n - k))
    (decreases (n-k))
= if k + 1 = n then () else lemma_init_aux_len' #a n (k+1) contents

let lemma_init_len #_ n contents = if n = 0 then () else lemma_init_aux_len' n 0 contents

let lemma_init_aux_len = lemma_init_aux_len'

private let rec lemma_init_ghost_aux_len' (#a:Type) (n:nat) (k:nat{k < n}) (contents:(i:nat{ i < n } -> GTot a))
  : Lemma (requires True)
    (ensures (length (init_aux_ghost n k contents) = n - k))
    (decreases (n-k))
= if k + 1 = n then () else lemma_init_ghost_aux_len' #a n (k+1) contents

let lemma_init_ghost_len #_ n contents = if n = 0 then () else lemma_init_ghost_aux_len' n 0 contents

let lemma_init_ghost_aux_len = lemma_init_ghost_aux_len'

let rec lemma_len_upd #_ n v s = if n = 0 then () else lemma_len_upd (n - 1) v (tl s)

let lemma_len_append #_ s1 s2 = FStar.List.Tot.append_length (MkSeq?.l s1) (MkSeq?.l s2)

let rec lemma_len_slice' (#a:Type) (s:seq a) (i:nat) (j:nat{i <= j && j <= length s})
  : Lemma
    (requires True)
    (ensures (length (slice s i j) = j - i)) (decreases (length s))
= if i > 0 then lemma_len_slice' #a (tl s) (i - 1) (j - 1)
  else if j = 0 then ()
  else lemma_len_slice' #a (tl s) i (j - 1)

let lemma_len_slice = lemma_len_slice'

let rec lemma_index_create #_ n v i =
  if n = 0 then ()
  else if i = 0 then ()
       else (lemma_create_len (n - 1) v; lemma_index_create (n - 1) v (i - 1))

let rec lemma_index_upd1' (#a:Type) (s:seq a) (n:nat{n < length s}) (v:a)
  : Lemma
    (requires True)
val lemma_index_upd1' (#a: Type) (s: seq a) (n: nat{n < length s}) (v: a)
    : Lemma (requires True) (ensures (index (upd s n v) n == v)) (decreases (length s))
s: FStar.Seq.Base.seq a -> n: Prims.nat{n < FStar.Seq.Base.length s} -> v: a
  -> FStar.Pervasives.Lemma (ensures FStar.Seq.Base.index (FStar.Seq.Base.upd s n v) n == v)
      (decreases FStar.Seq.Base.length s)