# HG changeset patch
# User Cezary Kaliszyk <kaliszyk@in.tum.de>
# Date 1260051968 -3600
# Node ID baff284c6fcc027ff7b933eefa1f03af9169bbf3
# Parent  96c241932603bf085bd398582e149a2eed408082
Proved foldl_rsp and ho_map_rsp

diff -r 96c241932603 -r baff284c6fcc IntEx.thy
--- a/IntEx.thy	Sat Dec 05 22:38:42 2009 +0100
+++ b/IntEx.thy	Sat Dec 05 23:26:08 2009 +0100
@@ -159,7 +159,6 @@
 apply(tactic {* procedure_tac @{context} @{thm test1} 1 *})
 apply(tactic {* regularize_tac @{context} [rel_eqv] 1 *})
 apply(tactic {* all_inj_repabs_tac_intex @{context} 1*})
-apply(tactic {* simp_tac (HOL_basic_ss addSolver quotient_solver addsimps @{thms all_prs})  1 *})
 apply(tactic {* clean_tac @{context} 1 *}) 
 done
 
@@ -214,22 +213,6 @@
 apply simp
 done
 
-(* I believe it's true. *)
-lemma foldl_rsp[quotient_rsp]:
-  "((op \<approx> ===> op \<approx> ===> op \<approx>) ===> op \<approx> ===> list_rel op \<approx> ===> op \<approx>) foldl foldl"
-apply (simp only: fun_rel.simps)
-apply (rule allI)
-apply (rule allI)
-apply (rule impI)
-apply (rule allI)
-apply (rule allI)
-apply (rule impI)
-apply (rule allI)
-apply (rule allI)
-apply (rule impI)
-apply (induct_tac xb yb rule: list_induct2) (* To finish I need to give it: arbitrary:xa ya *)
-sorry
-
 lemma "foldl PLUS x [] = x"
 apply(tactic {* procedure_tac @{context} @{thm ho_tst} 1 *})
 apply(tactic {* regularize_tac @{context} [rel_eqv] 1 *})
diff -r 96c241932603 -r baff284c6fcc QuotList.thy
--- a/QuotList.thy	Sat Dec 05 22:38:42 2009 +0100
+++ b/QuotList.thy	Sat Dec 05 23:26:08 2009 +0100
@@ -84,10 +84,22 @@
   shows "(map abs2) (map ((abs1 ---> rep2) f) (map rep1 l)) = map f l"
 by (induct l) (simp_all add: Quotient_abs_rep[OF a] Quotient_abs_rep[OF b])
 
-(* We need an ho version *)
 lemma map_rsp:
   assumes q1: "Quotient R1 Abs1 Rep1"
   and     q2: "Quotient R2 Abs2 Rep2"
+  shows "((R1 ===> R2) ===> (list_rel R1) ===> list_rel R2) map map"
+apply(simp)
+apply(rule allI)+
+apply(rule impI)
+apply(rule allI)+
+apply (induct_tac xa ya rule: list_induct2')
+apply simp_all
+done
+
+(* TODO: if the above is correct, we can remove this one *)
+lemma map_rsp_lo:
+  assumes q1: "Quotient R1 Abs1 Rep1"
+  and     q2: "Quotient R2 Abs2 Rep2"
   and     a: "(R1 ===> R2) f1 f2"
   and     b: "list_rel R1 l1 l2"
   shows "list_rel R2 (map f1 l1) (map f2 l2)"
@@ -106,8 +118,35 @@
   shows "abs1 (foldl ((abs1 ---> abs2 ---> rep1) f) (rep1 e) (map rep2 l)) = foldl f e l"
 by (induct l arbitrary:e) (simp_all add: Quotient_abs_rep[OF a] Quotient_abs_rep[OF b])
 
+lemma list_rel_empty: "list_rel R [] b \<Longrightarrow> length b = 0"
+by (induct b) (simp_all)
 
+lemma list_rel_len: "list_rel R a b \<Longrightarrow> length a = length b"
+apply (induct a arbitrary: b)
+apply (simp add: list_rel_empty)
+apply (case_tac b)
+apply simp_all
+done
 
+(* TODO: induct_tac doesn't accept 'arbitrary'.
+         induct     doesn't accept 'rule'.
+   that's why the proof uses manual generalisation and needs assumptions
+   both in conclusion for induction and in assumptions. *)
+lemma foldl_rsp[quotient_rsp]:
+  assumes q1: "Quotient R1 Abs1 Rep1"
+  and     q2: "Quotient R2 Abs2 Rep2"
+  shows "((R1 ===> R2 ===> R1) ===> R1 ===> list_rel R2 ===> R1) foldl foldl"
+apply auto
+apply (subgoal_tac "R1 xa ya \<longrightarrow> list_rel R2 xb yb \<longrightarrow> R1 (foldl x xa xb) (foldl y ya yb)")
+apply simp
+apply (rule_tac x="xa" in spec)
+apply (rule_tac x="ya" in spec)
+apply (rule_tac xs="xb" and ys="yb" in list_induct2)
+apply (rule list_rel_len)
+apply (simp_all)
+done
+
+(* TODO: foldr_rsp should be similar *)