val lemma_hprefix_append_telem (#a:Type) (s: seq a{length s > 0}):
  Lemma (ensures (let s' = hprefix s in
                  let e = telem s in
                  s == append1 s' e))
        [SMTPat (hprefix s); SMTPat (prefix s (length s - 1))]
val lemma_hprefix_append_telem (#a:Type) (s: seq a{length s > 0}):
  Lemma (ensures (let s' = hprefix s in
                  let e = telem s in
                  s == append1 s' e))
        [SMTPat (hprefix s); SMTPat (prefix s (length s - 1))]
let lemma_hprefix_append_telem (#a:Type) (s: seq a{length s > 0}):
  Lemma (ensures (let s' = hprefix s in
                  let e = telem s in
                  s == append1 s' e)) =
  let s' = hprefix s in
  let e = telem s in
  lemma_prefix1_append s' e;
  let s2 = append1 s' e in
  assert(length s = length s2);
  let aux (i: seq_index s):
    Lemma (ensures (index s i == index s2 i))
          [SMTPat (index s i == index s2 i)] = ()
  in
  lemma_eq_intro s s2
module Zeta.SeqAux
#push-options "--print_universes"

open FStar.Classical
open FStar.Seq
open FStar.Squash

let prefix (#a:Type) (s:seq a) (i:nat{i <= length s}) = slice s 0 i

let prefix_slice #_ _ _ = ()

let lemma_prefix_index (#a:Type) (s:seq a) (i:nat{i <= length s}) (j:nat{j < i}):
  Lemma (requires (True))
        (ensures (index (prefix s i) j == index s j)) =
  lemma_index_slice s 0 i j

let lemma_prefix_prefix (#a:Type) (s:seq a) (i:nat{i <= length s}) (j:nat{j <= i}):
  Lemma (requires (True))
        (ensures (prefix (prefix s i) j == prefix s j)) =
  let pij = prefix (prefix s i) j in
  let pj = prefix s j in
  let pi = prefix s i in
  let aux (k:nat{k < j}):
    Lemma (index pij k == index pj k) =
    lemma_prefix_index s j k;
    lemma_prefix_index s i k;
    lemma_prefix_index pi j k
  in
  forall_intro aux; lemma_eq_intro pij pj

let lemma_fullprefix_equal (#a:Type) (s:seq a):
  Lemma (requires (True))
        (ensures (prefix s (length s) == s)) =
  let n = length s in
  let p = prefix s n in
  let aux (k:nat{k < n}):
    Lemma (index p k == index s k) =
    lemma_prefix_index s n k
  in
  forall_intro aux; lemma_eq_intro s p

let lemma_prefix_append (#a:Type) (s1 s2: seq a):
  Lemma (prefix (append s1 s2) (length s1) == s1) =
  // triggers an SMT pat that provides what we need
  assert(equal (prefix (append s1 s2) (length s1)) s1);
  ()
/
prims.fst.checked FStar.Squash.fsti.checked FStar.Seq.fst.checked FStar.Pervasives.Native.fst.checked FStar.Pervasives.fsti.checked FStar.Classical.Sugar.fsti.checked FStar.Classical.fsti.checked FStar.Calc.fsti.checked
Zeta.SeqAux.fst
s: FStar.Seq.Base.seq a {FStar.Seq.Base.length s > 0}
  -> FStar.Pervasives.Lemma
      (ensures
        (let s' = Zeta.SeqAux.hprefix s in
          let e = Zeta.SeqAux.telem s in
          s == Zeta.SeqAux.append1 s' e))
      [SMTPat (Zeta.SeqAux.hprefix s); SMTPat (Zeta.SeqAux.prefix s (FStar.Seq.Base.length s - 1))]
FStar.Seq.Base.seq Prims.b2t Prims.op_GreaterThan FStar.Seq.Base.length FStar.Seq.Base.lemma_eq_intro Zeta.SeqAux.seq_index Prims.unit Prims.l_True Prims.squash Prims.eq2 FStar.Seq.Base.index Prims.Cons FStar.Pervasives.pattern FStar.Pervasives.smt_pat Prims.logical Prims.Nil Prims._assert Prims.op_Equality Prims.nat Prims.int Prims.op_Addition Zeta.SeqAux.append1 Zeta.SeqAux.lemma_prefix1_append Zeta.SeqAux.telem Zeta.SeqAux.hprefix Prims.l_or
let lemma_hprefix_append_telem (#a: Type) (s: seq a {length s > 0})
    : Lemma
    (ensures
      (let s' = hprefix s in
        let e = telem s in
        s == append1 s' e)) =
  
let s' = hprefix s in
let e = telem s in
lemma_prefix1_append s' e;
let s2 = append1 s' e in
assert (length s = length s2);
let aux (i: seq_index s)
    : Lemma (ensures (index s i == index s2 i)) [SMTPat (index s i == index s2 i)] =
  ()
in
lemma_eq_intro s s2