diff -r 0384e039b7f2 -r e121ac0028f8 QuotList.thy
--- a/QuotList.thy	Sun Dec 06 00:13:35 2009 +0100
+++ b/QuotList.thy	Sun Dec 06 00:19:45 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:
+  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 *)