src/HOL/List.thy
changeset 22633 a47e4fd7ebc1
parent 22551 e52f5400e331
child 22793 dc13dfd588b2
equal deleted inserted replaced
22632:59c117a0bcf3 22633:a47e4fd7ebc1
   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 *}