(* 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)