Theory Stream

Up to index of Isabelle/CCL/ex

theory Stream
imports List
uses [Stream.ML]
begin

(*  Title:      CCL/ex/Stream.thy
    ID:         $Id: Stream.thy,v 1.4 2005/09/17 15:35:32 wenzelm Exp $
    Author:     Martin Coen, Cambridge University Computer Laboratory
    Copyright   1993  University of Cambridge
*)

header {* Programs defined over streams *}

theory Stream
imports List
begin

consts
  iter1   ::  "[i=>i,i]=>i"
  iter2   ::  "[i=>i,i]=>i"

defs

  iter1_def:   "iter1(f,a) == letrec iter x be x$iter(f(x)) in iter(a)"
  iter2_def:   "iter2(f,a) == letrec iter x be x$map(f,iter(x)) in iter(a)"

ML {* use_legacy_bindings (the_context ()) *}

end

theorem map_comp:

  l : Lists(A) ==> map(f o g, l) = map(f, map(g, l))

theorem map_id:

  l : Lists(A) ==> map(%x. x, l) = l

theorem map_append:

  [| l : Lists(A); m : Lists(A) |] ==> map(f, l @ m) = map(f, l) @ map(f, m)

theorem append_assoc:

  [| k : Lists(A); l : Lists(A); m : Lists(A) |] ==> k @ l @ m = (k @ l) @ m

theorem ilist_append:

  l : ILists(A) ==> l @ m = l

theorem iter1B:

  iter1(f, a) = a $ iter1(f, f(a))

theorem iter2B:

  iter2(f, a) = a $ map(f, iter2(f, a))

theorem iter2Blemma:

  n : Nat
  ==> map(f) ^ n ` iter2(f, a) = (f ^ n ` a) $ (map(f) ^ n ` map(f, iter2(f, a)))

theorem iter1_iter2_eq:

  iter1(f, a) = iter2(f, a)