src/HOL/Imperative_HOL/ex/Sublist.thy
changeset 41842 d8f76db6a207
parent 41413 64cd30d6b0b8
child 44890 22f665a2e91c
equal deleted inserted replaced
41840:f69045fdc836 41842:d8f76db6a207
   419 
   419 
   420 lemma sublist'_back: "\<lbrakk> i < j; j \<le> length xs \<rbrakk> \<Longrightarrow> sublist' i j xs = sublist' i (j - 1) xs @ [xs ! (j - 1)]"
   420 lemma sublist'_back: "\<lbrakk> i < j; j \<le> length xs \<rbrakk> \<Longrightarrow> sublist' i j xs = sublist' i (j - 1) xs @ [xs ! (j - 1)]"
   421 apply (induct xs arbitrary: a i j)
   421 apply (induct xs arbitrary: a i j)
   422 apply simp
   422 apply simp
   423 apply simp
   423 apply simp
   424 apply (case_tac j)
       
   425 apply simp
       
   426 apply auto
       
   427 apply (case_tac nat)
       
   428 apply auto
       
   429 done
   424 done
   430 
   425 
   431 (* suffices that j \<le> length xs and length ys *) 
   426 (* suffices that j \<le> length xs and length ys *) 
   432 lemma sublist'_eq_samelength_iff: "length xs = length ys \<Longrightarrow> (sublist' i j xs  = sublist' i j ys) = (\<forall>i'. i \<le> i' \<and> i' < j \<longrightarrow> xs ! i' = ys ! i')"
   427 lemma sublist'_eq_samelength_iff: "length xs = length ys \<Longrightarrow> (sublist' i j xs  = sublist' i j ys) = (\<forall>i'. i \<le> i' \<and> i' < j \<longrightarrow> xs ! i' = ys ! i')"
   433 proof (induct xs arbitrary: ys i j)
   428 proof (induct xs arbitrary: ys i j)
   441     apply simp
   436     apply simp
   442     apply auto
   437     apply auto
   443     apply (case_tac i', auto)
   438     apply (case_tac i', auto)
   444     apply (erule_tac x="Suc i'" in allE, auto)
   439     apply (erule_tac x="Suc i'" in allE, auto)
   445     apply (erule_tac x="i' - 1" in allE, auto)
   440     apply (erule_tac x="i' - 1" in allE, auto)
   446     apply (case_tac i', auto)
       
   447     apply (erule_tac x="Suc i'" in allE, auto)
   441     apply (erule_tac x="Suc i'" in allE, auto)
   448     done
   442     done
   449 qed
   443 qed
   450 
   444 
   451 lemma sublist'_all[simp]: "sublist' 0 (length xs) xs = xs"
   445 lemma sublist'_all[simp]: "sublist' 0 (length xs) xs = xs"
   457 lemma sublist'_append: "\<lbrakk> i \<le> j; j \<le> k \<rbrakk> \<Longrightarrow>(sublist' i j xs) @ (sublist' j k xs) = sublist' i k xs"
   451 lemma sublist'_append: "\<lbrakk> i \<le> j; j \<le> k \<rbrakk> \<Longrightarrow>(sublist' i j xs) @ (sublist' j k xs) = sublist' i k xs"
   458 by (induct xs arbitrary: i j k) auto
   452 by (induct xs arbitrary: i j k) auto
   459 
   453 
   460 lemma nth_sublist': "\<lbrakk> k < j - i; j \<le> length xs \<rbrakk> \<Longrightarrow> (sublist' i j xs) ! k = xs ! (i + k)"
   454 lemma nth_sublist': "\<lbrakk> k < j - i; j \<le> length xs \<rbrakk> \<Longrightarrow> (sublist' i j xs) ! k = xs ! (i + k)"
   461 apply (induct xs arbitrary: i j k)
   455 apply (induct xs arbitrary: i j k)
   462 apply auto
   456 apply simp
   463 apply (case_tac k)
   457 apply (case_tac k)
   464 apply auto
       
   465 apply (case_tac i)
       
   466 apply auto
   458 apply auto
   467 done
   459 done
   468 
   460 
   469 lemma set_sublist': "set (sublist' i j xs) = {x. \<exists>k. i \<le> k \<and> k < j \<and> k < List.length xs \<and> x = xs ! k}"
   461 lemma set_sublist': "set (sublist' i j xs) = {x. \<exists>k. i \<le> k \<and> k < j \<and> k < List.length xs \<and> x = xs ! k}"
   470 apply (simp add: sublist'_sublist)
   462 apply (simp add: sublist'_sublist)