297 of those of the other list and there are fewer Cons's in one than the other. |
297 of those of the other list and there are fewer Cons's in one than the other. |
298 *) |
298 *) |
299 ML_setup {* |
299 ML_setup {* |
300 local |
300 local |
301 |
301 |
302 val neq_if_length_neq = thm "neq_if_length_neq"; |
|
303 |
|
304 fun len (Const("List.list.Nil",_)) acc = acc |
302 fun len (Const("List.list.Nil",_)) acc = acc |
305 | len (Const("List.list.Cons",_) $ _ $ xs) (ts,n) = len xs (ts,n+1) |
303 | len (Const("List.list.Cons",_) $ _ $ xs) (ts,n) = len xs (ts,n+1) |
306 | len (Const("List.op @",_) $ xs $ ys) acc = len xs (len ys acc) |
304 | len (Const("List.op @",_) $ xs $ ys) acc = len xs (len ys acc) |
307 | len (Const("List.rev",_) $ xs) acc = len xs acc |
305 | len (Const("List.rev",_) $ xs) acc = len xs acc |
308 | len (Const("List.map",_) $ _ $ xs) acc = len xs acc |
306 | len (Const("List.map",_) $ _ $ xs) acc = len xs acc |
309 | len t (ts,n) = (t::ts,n); |
307 | len t (ts,n) = (t::ts,n); |
310 |
|
311 val list_ss = simpset_of(the_context()); |
|
312 |
308 |
313 fun list_eq ss (Const(_,eqT) $ lhs $ rhs) = |
309 fun list_eq ss (Const(_,eqT) $ lhs $ rhs) = |
314 let |
310 let |
315 val (ls,m) = len lhs ([],0) and (rs,n) = len rhs ([],0); |
311 val (ls,m) = len lhs ([],0) and (rs,n) = len rhs ([],0); |
316 fun prove_neq() = |
312 fun prove_neq() = |
318 val Type(_,listT::_) = eqT; |
314 val Type(_,listT::_) = eqT; |
319 val size = Const("Nat.size", listT --> HOLogic.natT); |
315 val size = Const("Nat.size", listT --> HOLogic.natT); |
320 val eq_len = HOLogic.mk_eq (size $ lhs, size $ rhs); |
316 val eq_len = HOLogic.mk_eq (size $ lhs, size $ rhs); |
321 val neq_len = HOLogic.mk_Trueprop (HOLogic.Not $ eq_len); |
317 val neq_len = HOLogic.mk_Trueprop (HOLogic.Not $ eq_len); |
322 val thm = Goal.prove (Simplifier.the_context ss) [] [] neq_len |
318 val thm = Goal.prove (Simplifier.the_context ss) [] [] neq_len |
323 (K (simp_tac (Simplifier.inherit_context ss list_ss) 1)); |
319 (K (simp_tac (Simplifier.inherit_context ss @{simpset}) 1)); |
324 in SOME (thm RS neq_if_length_neq) end |
320 in SOME (thm RS @{thm neq_if_length_neq}) end |
325 in |
321 in |
326 if m < n andalso gen_submultiset (op aconv) (ls,rs) orelse |
322 if m < n andalso gen_submultiset (op aconv) (ls,rs) orelse |
327 n < m andalso gen_submultiset (op aconv) (rs,ls) |
323 n < m andalso gen_submultiset (op aconv) (rs,ls) |
328 then prove_neq() else NONE |
324 then prove_neq() else NONE |
329 end; |
325 end; |
330 |
326 |
331 in |
327 in |
332 |
328 |
333 val list_neq_simproc = |
329 val list_neq_simproc = |
334 Simplifier.simproc (the_context ()) "list_neq" ["(xs::'a list) = ys"] (K list_eq); |
330 Simplifier.simproc @{theory} "list_neq" ["(xs::'a list) = ys"] (K list_eq); |
335 |
331 |
336 end; |
332 end; |
337 |
333 |
338 Addsimprocs [list_neq_simproc]; |
334 Addsimprocs [list_neq_simproc]; |
339 *} |
335 *} |
439 *} |
435 *} |
440 |
436 |
441 ML_setup {* |
437 ML_setup {* |
442 local |
438 local |
443 |
439 |
444 val append_assoc = thm "append_assoc"; |
|
445 val append_Nil = thm "append_Nil"; |
|
446 val append_Cons = thm "append_Cons"; |
|
447 val append1_eq_conv = thm "append1_eq_conv"; |
|
448 val append_same_eq = thm "append_same_eq"; |
|
449 |
|
450 fun last (cons as Const("List.list.Cons",_) $ _ $ xs) = |
440 fun last (cons as Const("List.list.Cons",_) $ _ $ xs) = |
451 (case xs of Const("List.list.Nil",_) => cons | _ => last xs) |
441 (case xs of Const("List.list.Nil",_) => cons | _ => last xs) |
452 | last (Const("List.op @",_) $ _ $ ys) = last ys |
442 | last (Const("List.op @",_) $ _ $ ys) = last ys |
453 | last t = t; |
443 | last t = t; |
454 |
444 |
458 fun butlast ((cons as Const("List.list.Cons",_) $ x) $ xs) = |
448 fun butlast ((cons as Const("List.list.Cons",_) $ x) $ xs) = |
459 (case xs of Const("List.list.Nil",_) => xs | _ => cons $ butlast xs) |
449 (case xs of Const("List.list.Nil",_) => xs | _ => cons $ butlast xs) |
460 | butlast ((app as Const("List.op @",_) $ xs) $ ys) = app $ butlast ys |
450 | butlast ((app as Const("List.op @",_) $ xs) $ ys) = app $ butlast ys |
461 | butlast xs = Const("List.list.Nil",fastype_of xs); |
451 | butlast xs = Const("List.list.Nil",fastype_of xs); |
462 |
452 |
463 val rearr_ss = HOL_basic_ss addsimps [append_assoc, append_Nil, append_Cons]; |
453 val rearr_ss = HOL_basic_ss addsimps [@{thm append_assoc}, |
|
454 @{thm append_Nil}, @{thm append_Cons}]; |
464 |
455 |
465 fun list_eq ss (F as (eq as Const(_,eqT)) $ lhs $ rhs) = |
456 fun list_eq ss (F as (eq as Const(_,eqT)) $ lhs $ rhs) = |
466 let |
457 let |
467 val lastl = last lhs and lastr = last rhs; |
458 val lastl = last lhs and lastr = last rhs; |
468 fun rearr conv = |
459 fun rearr conv = |
476 val thm = Goal.prove (Simplifier.the_context ss) [] [] eq |
467 val thm = Goal.prove (Simplifier.the_context ss) [] [] eq |
477 (K (simp_tac (Simplifier.inherit_context ss rearr_ss) 1)); |
468 (K (simp_tac (Simplifier.inherit_context ss rearr_ss) 1)); |
478 in SOME ((conv RS (thm RS trans)) RS eq_reflection) end; |
469 in SOME ((conv RS (thm RS trans)) RS eq_reflection) end; |
479 |
470 |
480 in |
471 in |
481 if list1 lastl andalso list1 lastr then rearr append1_eq_conv |
472 if list1 lastl andalso list1 lastr then rearr @{thm append1_eq_conv} |
482 else if lastl aconv lastr then rearr append_same_eq |
473 else if lastl aconv lastr then rearr @{thm append_same_eq} |
483 else NONE |
474 else NONE |
484 end; |
475 end; |
485 |
476 |
486 in |
477 in |
487 |
478 |
488 val list_eq_simproc = |
479 val list_eq_simproc = |
489 Simplifier.simproc (the_context ()) "list_eq" ["(xs::'a list) = ys"] (K list_eq); |
480 Simplifier.simproc @{theory} "list_eq" ["(xs::'a list) = ys"] (K list_eq); |
490 |
481 |
491 end; |
482 end; |
492 |
483 |
493 Addsimprocs [list_eq_simproc]; |
484 Addsimprocs [list_eq_simproc]; |
494 *} |
485 *} |