src/HOL/Library/Dlist.thy
changeset 62390 842917225d56
parent 62324 ae44f16dcea5
child 63375 59803048b0e8
equal deleted inserted replaced
62380:29800666e526 62390:842917225d56
   239   shows "P xs ys"
   239   shows "P xs ys"
   240 using eq
   240 using eq
   241 proof(induction xs ys rule: wpull.induct)
   241 proof(induction xs ys rule: wpull.induct)
   242   case 1 thus ?case by(simp add: Nil)
   242   case 1 thus ?case by(simp add: Nil)
   243 next
   243 next
   244   case 2 thus ?case by(simp split: split_if_asm)
   244   case 2 thus ?case by(simp split: if_split_asm)
   245 next
   245 next
   246   case Cons: (3 a b xs b' c ys)
   246   case Cons: (3 a b xs b' c ys)
   247   let ?xs = "(a, b) # xs" and ?ys = "(b', c) # ys"
   247   let ?xs = "(a, b) # xs" and ?ys = "(b', c) # ys"
   248   consider (xs) "b \<in> snd ` set xs" | (ys) "b \<notin> snd ` set xs" "b' \<in> fst ` set ys"
   248   consider (xs) "b \<in> snd ` set xs" | (ys) "b \<notin> snd ` set xs" "b' \<in> fst ` set ys"
   249     | (step) "b \<notin> snd ` set xs" "b' \<notin> fst ` set ys" by auto
   249     | (step) "b \<notin> snd ` set xs" "b' \<notin> fst ` set ys" by auto
   252     case xs
   252     case xs
   253     with Cons.prems have eq: "remdups (map snd xs) = remdups (map fst ?ys)" by auto
   253     with Cons.prems have eq: "remdups (map snd xs) = remdups (map fst ?ys)" by auto
   254     from xs eq have "b \<in> fst ` set ?ys" by (metis list.set_map set_remdups)
   254     from xs eq have "b \<in> fst ` set ?ys" by (metis list.set_map set_remdups)
   255     hence "map_of (rev ?ys) b \<noteq> None" unfolding map_of_eq_None_iff by auto
   255     hence "map_of (rev ?ys) b \<noteq> None" unfolding map_of_eq_None_iff by auto
   256     then obtain c' where "map_of (rev ?ys) b = Some c'" by blast
   256     then obtain c' where "map_of (rev ?ys) b = Some c'" by blast
   257     then have "(b, the (map_of (rev ?ys) b)) \<in> set ?ys" by(auto dest: map_of_SomeD split: split_if_asm)
   257     then have "(b, the (map_of (rev ?ys) b)) \<in> set ?ys" by(auto dest: map_of_SomeD split: if_split_asm)
   258     from xs eq this Cons.IH(1)[OF xs eq] show ?thesis by(rule left)
   258     from xs eq this Cons.IH(1)[OF xs eq] show ?thesis by(rule left)
   259   next
   259   next
   260     case ys
   260     case ys
   261     from ys Cons.prems have eq: "remdups (map snd ?xs) = remdups (map fst ys)" by auto
   261     from ys Cons.prems have eq: "remdups (map snd ?xs) = remdups (map fst ys)" by auto
   262     from ys eq have "b' \<in> snd ` set ?xs" by (metis list.set_map set_remdups)
   262     from ys eq have "b' \<in> snd ` set ?xs" by (metis list.set_map set_remdups)
   263     hence "map_of (map prod.swap (rev ?xs)) b' \<noteq> None"
   263     hence "map_of (map prod.swap (rev ?xs)) b' \<noteq> None"
   264       unfolding map_of_eq_None_iff by(auto simp add: image_image)
   264       unfolding map_of_eq_None_iff by(auto simp add: image_image)
   265     then obtain a' where "map_of (map prod.swap (rev ?xs)) b' = Some a'" by blast
   265     then obtain a' where "map_of (map prod.swap (rev ?xs)) b' = Some a'" by blast
   266     then have "(the (map_of (map prod.swap (rev ?xs)) b'), b') \<in> set ?xs"
   266     then have "(the (map_of (map prod.swap (rev ?xs)) b'), b') \<in> set ?xs"
   267       by(auto dest: map_of_SomeD split: split_if_asm)
   267       by(auto dest: map_of_SomeD split: if_split_asm)
   268     from ys eq this Cons.IH(2)[OF ys eq] show ?thesis by(rule right)
   268     from ys eq this Cons.IH(2)[OF ys eq] show ?thesis by(rule right)
   269   next
   269   next
   270     case *: step
   270     case *: step
   271     hence "remdups (map snd xs) = remdups (map fst ys)" "b = b'" using Cons.prems by auto
   271     hence "remdups (map snd xs) = remdups (map fst ys)" "b = b'" using Cons.prems by auto
   272     from * this(1) Cons.IH(3)[OF * this(1)] show ?thesis unfolding \<open>b = b'\<close> by(rule step)
   272     from * this(1) Cons.IH(3)[OF * this(1)] show ?thesis unfolding \<open>b = b'\<close> by(rule step)