src/HOL/Nitpick_Examples/Manual_Nits.thy
changeset 42959 ee829022381d
parent 42421 6bc725d60593
child 45035 60d2c03d5c70
equal deleted inserted replaced
42958:034fc4d0c909 42959:ee829022381d
    42 nitpick [dont_specialize, show_consts, expect = genuine]
    42 nitpick [dont_specialize, show_consts, expect = genuine]
    43 oops
    43 oops
    44 
    44 
    45 lemma "\<exists>!x. P x \<Longrightarrow> P (THE y. P y)"
    45 lemma "\<exists>!x. P x \<Longrightarrow> P (THE y. P y)"
    46 nitpick [expect = none]
    46 nitpick [expect = none]
    47 nitpick [card 'a = 1\<midarrow>50, expect = none]
    47 nitpick [card 'a = 1\<emdash>50, expect = none]
    48 (* sledgehammer *)
    48 (* sledgehammer *)
    49 apply (metis the_equality)
    49 apply (metis the_equality)
    50 done
    50 done
    51 
    51 
    52 subsection {* 3.4. Skolemization *}
    52 subsection {* 3.4. Skolemization *}
   225 nitpick [verbose, expect = genuine]
   225 nitpick [verbose, expect = genuine]
   226 oops
   226 oops
   227 
   227 
   228 lemma "\<lbrakk>xs = LCons a xs; ys = LCons a ys\<rbrakk> \<Longrightarrow> xs = ys"
   228 lemma "\<lbrakk>xs = LCons a xs; ys = LCons a ys\<rbrakk> \<Longrightarrow> xs = ys"
   229 nitpick [bisim_depth = -1, show_datatypes, expect = quasi_genuine]
   229 nitpick [bisim_depth = -1, show_datatypes, expect = quasi_genuine]
   230 nitpick [card = 1\<midarrow>5, expect = none]
   230 nitpick [card = 1\<emdash>5, expect = none]
   231 sorry
   231 sorry
   232 
   232 
   233 subsection {* 3.10. Boxing *}
   233 subsection {* 3.10. Boxing *}
   234 
   234 
   235 datatype tm = Var nat | Lam tm | App tm tm
   235 datatype tm = Var nat | Lam tm | App tm tm
   261 "subst\<^isub>2 \<sigma> (Lam t) =
   261 "subst\<^isub>2 \<sigma> (Lam t) =
   262  Lam (subst\<^isub>2 (\<lambda>n. case n of 0 \<Rightarrow> Var 0 | Suc m \<Rightarrow> lift (\<sigma> m) 0) t)" |
   262  Lam (subst\<^isub>2 (\<lambda>n. case n of 0 \<Rightarrow> Var 0 | Suc m \<Rightarrow> lift (\<sigma> m) 0) t)" |
   263 "subst\<^isub>2 \<sigma> (App t u) = App (subst\<^isub>2 \<sigma> t) (subst\<^isub>2 \<sigma> u)"
   263 "subst\<^isub>2 \<sigma> (App t u) = App (subst\<^isub>2 \<sigma> t) (subst\<^isub>2 \<sigma> u)"
   264 
   264 
   265 lemma "\<not> loose t 0 \<Longrightarrow> subst\<^isub>2 \<sigma> t = t"
   265 lemma "\<not> loose t 0 \<Longrightarrow> subst\<^isub>2 \<sigma> t = t"
   266 nitpick [card = 1\<midarrow>5, expect = none]
   266 nitpick [card = 1\<emdash>5, expect = none]
   267 sorry
   267 sorry
   268 
   268 
   269 subsection {* 3.11. Scope Monotonicity *}
   269 subsection {* 3.11. Scope Monotonicity *}
   270 
   270 
   271 lemma "length xs = length ys \<Longrightarrow> rev (zip xs ys) = zip xs (rev ys)"
   271 lemma "length xs = length ys \<Longrightarrow> rev (zip xs ys) = zip xs (rev ys)"
   286 
   286 
   287 lemma "n \<in> reach \<Longrightarrow> 2 dvd n"
   287 lemma "n \<in> reach \<Longrightarrow> 2 dvd n"
   288 (* nitpick *)
   288 (* nitpick *)
   289 apply (induct set: reach)
   289 apply (induct set: reach)
   290   apply auto
   290   apply auto
   291  nitpick [card = 1\<midarrow>4, bits = 1\<midarrow>4, expect = none]
   291  nitpick [card = 1\<emdash>4, bits = 1\<emdash>4, expect = none]
   292  apply (thin_tac "n \<in> reach")
   292  apply (thin_tac "n \<in> reach")
   293  nitpick [expect = genuine]
   293  nitpick [expect = genuine]
   294 oops
   294 oops
   295 
   295 
   296 lemma "n \<in> reach \<Longrightarrow> 2 dvd n \<and> n \<noteq> 0"
   296 lemma "n \<in> reach \<Longrightarrow> 2 dvd n \<and> n \<noteq> 0"
   297 (* nitpick *)
   297 (* nitpick *)
   298 apply (induct set: reach)
   298 apply (induct set: reach)
   299   apply auto
   299   apply auto
   300  nitpick [card = 1\<midarrow>4, bits = 1\<midarrow>4, expect = none]
   300  nitpick [card = 1\<emdash>4, bits = 1\<emdash>4, expect = none]
   301  apply (thin_tac "n \<in> reach")
   301  apply (thin_tac "n \<in> reach")
   302  nitpick [expect = genuine]
   302  nitpick [expect = genuine]
   303 oops
   303 oops
   304 
   304 
   305 lemma "n \<in> reach \<Longrightarrow> 2 dvd n \<and> n \<ge> 4"
   305 lemma "n \<in> reach \<Longrightarrow> 2 dvd n \<and> n \<ge> 4"
   334 (* nitpick *)
   334 (* nitpick *)
   335 proof (induct t)
   335 proof (induct t)
   336   case Leaf thus ?case by simp
   336   case Leaf thus ?case by simp
   337 next
   337 next
   338   case (Branch t u) thus ?case
   338   case (Branch t u) thus ?case
   339   nitpick [non_std, card = 1\<midarrow>4, expect = none]
   339   nitpick [non_std, card = 1\<emdash>4, expect = none]
   340   by auto
   340   by auto
   341 qed
   341 qed
   342 
   342 
   343 section {* 4. Case Studies *}
   343 section {* 4. Case Studies *}
   344 
   344 
   382 | "w \<in> S\<^isub>3 \<Longrightarrow> b # w \<in> B\<^isub>3"
   382 | "w \<in> S\<^isub>3 \<Longrightarrow> b # w \<in> B\<^isub>3"
   383 | "\<lbrakk>v \<in> B\<^isub>3; w \<in> B\<^isub>3\<rbrakk> \<Longrightarrow> a # v @ w \<in> B\<^isub>3"
   383 | "\<lbrakk>v \<in> B\<^isub>3; w \<in> B\<^isub>3\<rbrakk> \<Longrightarrow> a # v @ w \<in> B\<^isub>3"
   384 
   384 
   385 theorem S\<^isub>3_sound:
   385 theorem S\<^isub>3_sound:
   386 "w \<in> S\<^isub>3 \<longrightarrow> length [x \<leftarrow> w. x = a] = length [x \<leftarrow> w. x = b]"
   386 "w \<in> S\<^isub>3 \<longrightarrow> length [x \<leftarrow> w. x = a] = length [x \<leftarrow> w. x = b]"
   387 nitpick [card = 1\<midarrow>5, expect = none]
   387 nitpick [card = 1\<emdash>5, expect = none]
   388 sorry
   388 sorry
   389 
   389 
   390 theorem S\<^isub>3_complete:
   390 theorem S\<^isub>3_complete:
   391 "length [x \<leftarrow> w. x = a] = length [x \<leftarrow> w. x = b] \<longrightarrow> w \<in> S\<^isub>3"
   391 "length [x \<leftarrow> w. x = a] = length [x \<leftarrow> w. x = b] \<longrightarrow> w \<in> S\<^isub>3"
   392 nitpick [expect = genuine]
   392 nitpick [expect = genuine]
   401 | "w \<in> S\<^isub>4 \<Longrightarrow> b # w \<in> B\<^isub>4"
   401 | "w \<in> S\<^isub>4 \<Longrightarrow> b # w \<in> B\<^isub>4"
   402 | "\<lbrakk>v \<in> B\<^isub>4; w \<in> B\<^isub>4\<rbrakk> \<Longrightarrow> a # v @ w \<in> B\<^isub>4"
   402 | "\<lbrakk>v \<in> B\<^isub>4; w \<in> B\<^isub>4\<rbrakk> \<Longrightarrow> a # v @ w \<in> B\<^isub>4"
   403 
   403 
   404 theorem S\<^isub>4_sound:
   404 theorem S\<^isub>4_sound:
   405 "w \<in> S\<^isub>4 \<longrightarrow> length [x \<leftarrow> w. x = a] = length [x \<leftarrow> w. x = b]"
   405 "w \<in> S\<^isub>4 \<longrightarrow> length [x \<leftarrow> w. x = a] = length [x \<leftarrow> w. x = b]"
   406 nitpick [card = 1\<midarrow>5, expect = none]
   406 nitpick [card = 1\<emdash>5, expect = none]
   407 sorry
   407 sorry
   408 
   408 
   409 theorem S\<^isub>4_complete:
   409 theorem S\<^isub>4_complete:
   410 "length [x \<leftarrow> w. x = a] = length [x \<leftarrow> w. x = b] \<longrightarrow> w \<in> S\<^isub>4"
   410 "length [x \<leftarrow> w. x = a] = length [x \<leftarrow> w. x = b] \<longrightarrow> w \<in> S\<^isub>4"
   411 nitpick [card = 1\<midarrow>5, expect = none]
   411 nitpick [card = 1\<emdash>5, expect = none]
   412 sorry
   412 sorry
   413 
   413 
   414 theorem S\<^isub>4_A\<^isub>4_B\<^isub>4_sound_and_complete:
   414 theorem S\<^isub>4_A\<^isub>4_B\<^isub>4_sound_and_complete:
   415 "w \<in> S\<^isub>4 \<longleftrightarrow> length [x \<leftarrow> w. x = a] = length [x \<leftarrow> w. x = b]"
   415 "w \<in> S\<^isub>4 \<longleftrightarrow> length [x \<leftarrow> w. x = a] = length [x \<leftarrow> w. x = b]"
   416 "w \<in> A\<^isub>4 \<longleftrightarrow> length [x \<leftarrow> w. x = a] = length [x \<leftarrow> w. x = b] + 1"
   416 "w \<in> A\<^isub>4 \<longleftrightarrow> length [x \<leftarrow> w. x = a] = length [x \<leftarrow> w. x = b] + 1"
   417 "w \<in> B\<^isub>4 \<longleftrightarrow> length [x \<leftarrow> w. x = b] = length [x \<leftarrow> w. x = a] + 1"
   417 "w \<in> B\<^isub>4 \<longleftrightarrow> length [x \<leftarrow> w. x = b] = length [x \<leftarrow> w. x = a] + 1"
   418 nitpick [card = 1\<midarrow>5, expect = none]
   418 nitpick [card = 1\<emdash>5, expect = none]
   419 sorry
   419 sorry
   420 
   420 
   421 subsection {* 4.2. AA Trees *}
   421 subsection {* 4.2. AA Trees *}
   422 
   422 
   423 datatype 'a aa_tree = \<Lambda> | N "'a\<Colon>linorder" nat "'a aa_tree" "'a aa_tree"
   423 datatype 'a aa_tree = \<Lambda> | N "'a\<Colon>linorder" nat "'a aa_tree" "'a aa_tree"
   467     N x k t u)"
   467     N x k t u)"
   468 
   468 
   469 theorem dataset_skew_split:
   469 theorem dataset_skew_split:
   470 "dataset (skew t) = dataset t"
   470 "dataset (skew t) = dataset t"
   471 "dataset (split t) = dataset t"
   471 "dataset (split t) = dataset t"
   472 nitpick [card = 1\<midarrow>5, expect = none]
   472 nitpick [card = 1\<emdash>5, expect = none]
   473 sorry
   473 sorry
   474 
   474 
   475 theorem wf_skew_split:
   475 theorem wf_skew_split:
   476 "wf t \<Longrightarrow> skew t = t"
   476 "wf t \<Longrightarrow> skew t = t"
   477 "wf t \<Longrightarrow> split t = t"
   477 "wf t \<Longrightarrow> split t = t"
   478 nitpick [card = 1\<midarrow>5, expect = none]
   478 nitpick [card = 1\<emdash>5, expect = none]
   479 sorry
   479 sorry
   480 
   480 
   481 primrec insort\<^isub>1 where
   481 primrec insort\<^isub>1 where
   482 "insort\<^isub>1 \<Lambda> x = N x 1 \<Lambda> \<Lambda>" |
   482 "insort\<^isub>1 \<Lambda> x = N x 1 \<Lambda> \<Lambda>" |
   483 "insort\<^isub>1 (N y k t u) x =
   483 "insort\<^isub>1 (N y k t u) x =
   497 "insort\<^isub>2 (N y k t u) x =
   497 "insort\<^isub>2 (N y k t u) x =
   498  (split \<circ> skew) (N y k (if x < y then insort\<^isub>2 t x else t)
   498  (split \<circ> skew) (N y k (if x < y then insort\<^isub>2 t x else t)
   499                        (if x > y then insort\<^isub>2 u x else u))"
   499                        (if x > y then insort\<^isub>2 u x else u))"
   500 
   500 
   501 theorem wf_insort\<^isub>2: "wf t \<Longrightarrow> wf (insort\<^isub>2 t x)"
   501 theorem wf_insort\<^isub>2: "wf t \<Longrightarrow> wf (insort\<^isub>2 t x)"
   502 nitpick [card = 1\<midarrow>5, expect = none]
   502 nitpick [card = 1\<emdash>5, expect = none]
   503 sorry
   503 sorry
   504 
   504 
   505 theorem dataset_insort\<^isub>2: "dataset (insort\<^isub>2 t x) = {x} \<union> dataset t"
   505 theorem dataset_insort\<^isub>2: "dataset (insort\<^isub>2 t x) = {x} \<union> dataset t"
   506 nitpick [card = 1\<midarrow>5, expect = none]
   506 nitpick [card = 1\<emdash>5, expect = none]
   507 sorry
   507 sorry
   508 
   508 
   509 end
   509 end