src/HOL/List.thy
changeset 54404 9f0f1152c875
parent 54295 45a5523d4a63
child 54489 03ff4d1e6784
child 54496 178922b63b58
equal deleted inserted replaced
54403:40382f65bc80 54404:9f0f1152c875
   540 
   540 
   541 datatype termlets = If | Case of (typ * int)
   541 datatype termlets = If | Case of (typ * int)
   542 
   542 
   543 fun simproc ctxt redex =
   543 fun simproc ctxt redex =
   544   let
   544   let
   545     val thy = Proof_Context.theory_of ctxt
       
   546     val set_Nil_I = @{thm trans} OF [@{thm set.simps(1)}, @{thm empty_def}]
   545     val set_Nil_I = @{thm trans} OF [@{thm set.simps(1)}, @{thm empty_def}]
   547     val set_singleton = @{lemma "set [a] = {x. x = a}" by simp}
   546     val set_singleton = @{lemma "set [a] = {x. x = a}" by simp}
   548     val inst_Collect_mem_eq = @{lemma "set A = {x. x : set A}" by simp}
   547     val inst_Collect_mem_eq = @{lemma "set A = {x. x : set A}" by simp}
   549     val del_refl_eq = @{lemma "(t = t & P) == P" by simp}
   548     val del_refl_eq = @{lemma "(t = t & P) == P" by simp}
   550     fun mk_set T = Const (@{const_name List.set}, HOLogic.listT T --> HOLogic.mk_setT T)
   549     fun mk_set T = Const (@{const_name List.set}, HOLogic.listT T --> HOLogic.mk_setT T)
   561             (Const (@{const_name List.Nil}, _)) => s
   560             (Const (@{const_name List.Nil}, _)) => s
   562           | _ => (case s of SOME NONE => SOME (SOME i) | _ => NONE))
   561           | _ => (case s of SOME NONE => SOME (SOME i) | _ => NONE))
   563       in
   562       in
   564         fold_index check cases (SOME NONE) |> the_default NONE
   563         fold_index check cases (SOME NONE) |> the_default NONE
   565       end
   564       end
   566     (* returns (case_expr type index chosen_case) option  *)
   565     (* returns (case_expr type index chosen_case constr_name) option  *)
   567     fun dest_case case_term =
   566     fun dest_case case_term =
   568       let
   567       let
   569         val (case_const, args) = strip_comb case_term
   568         val (case_const, args) = strip_comb case_term
   570       in
   569       in
   571         (case try dest_Const case_const of
   570         (case try dest_Const case_const of
   572           SOME (c, T) =>
   571           SOME (c, T) =>
   573             (case Datatype.info_of_case thy c of
   572             (case Ctr_Sugar.ctr_sugar_of_case ctxt c of
   574               SOME _ =>
   573               SOME {ctrs, ...} =>
   575                 (case possible_index_of_singleton_case (fst (split_last args)) of
   574                 (case possible_index_of_singleton_case (fst (split_last args)) of
   576                   SOME i =>
   575                   SOME i =>
   577                     let
   576                     let
       
   577                       val constr_names = map (fst o dest_Const) ctrs
   578                       val (Ts, _) = strip_type T
   578                       val (Ts, _) = strip_type T
   579                       val T' = List.last Ts
   579                       val T' = List.last Ts
   580                     in SOME (List.last args, T', i, nth args i) end
   580                     in SOME (List.last args, T', i, nth args i, nth constr_names i) end
   581                 | NONE => NONE)
   581                 | NONE => NONE)
   582             | NONE => NONE)
   582             | NONE => NONE)
   583         | NONE => NONE)
   583         | NONE => NONE)
   584       end
   584       end
   585     (* returns condition continuing term option *)
   585     (* returns condition continuing term option *)
   603                 (HOLogic.conj_conv (Conv.rewr_conv (List.last prems RS @{thm Eq_FalseI})) Conv.all_conv
   603                 (HOLogic.conj_conv (Conv.rewr_conv (List.last prems RS @{thm Eq_FalseI})) Conv.all_conv
   604                  then_conv rewr_conv' @{lemma "(False & P) = False" by simp})) context) 1) ctxt 1
   604                  then_conv rewr_conv' @{lemma "(False & P) = False" by simp})) context) 1) ctxt 1
   605           THEN rtac set_Nil_I 1
   605           THEN rtac set_Nil_I 1
   606       | tac ctxt (Case (T, i) :: cont) =
   606       | tac ctxt (Case (T, i) :: cont) =
   607           let
   607           let
   608             val info = Datatype.the_info thy (fst (dest_Type T))
   608             val SOME {injects, distincts, case_thms, split, ...} =
       
   609               Ctr_Sugar.ctr_sugar_of ctxt (fst (dest_Type T))
   609           in
   610           in
   610             (* do case distinction *)
   611             (* do case distinction *)
   611             Splitter.split_tac [#split info] 1
   612             Splitter.split_tac [split] 1
   612             THEN EVERY (map_index (fn (i', _) =>
   613             THEN EVERY (map_index (fn (i', _) =>
   613               (if i' < length (#case_rewrites info) - 1 then rtac @{thm conjI} 1 else all_tac)
   614               (if i' < length case_thms - 1 then rtac @{thm conjI} 1 else all_tac)
   614               THEN REPEAT_DETERM (rtac @{thm allI} 1)
   615               THEN REPEAT_DETERM (rtac @{thm allI} 1)
   615               THEN rtac @{thm impI} 1
   616               THEN rtac @{thm impI} 1
   616               THEN (if i' = i then
   617               THEN (if i' = i then
   617                 (* continue recursively *)
   618                 (* continue recursively *)
   618                 Subgoal.FOCUS (fn {prems, context, ...} =>
   619                 Subgoal.FOCUS (fn {prems, context, ...} =>
   619                   CONVERSION (Thm.eta_conversion then_conv right_hand_set_comprehension_conv (K
   620                   CONVERSION (Thm.eta_conversion then_conv right_hand_set_comprehension_conv (K
   620                       ((HOLogic.conj_conv
   621                       ((HOLogic.conj_conv
   621                         (HOLogic.eq_conv Conv.all_conv (rewr_conv' (List.last prems)) then_conv
   622                         (HOLogic.eq_conv Conv.all_conv (rewr_conv' (List.last prems)) then_conv
   622                           (Conv.try_conv (Conv.rewrs_conv (map mk_meta_eq (#inject info)))))
   623                           (Conv.try_conv (Conv.rewrs_conv (map mk_meta_eq injects))))
   623                         Conv.all_conv)
   624                         Conv.all_conv)
   624                         then_conv (Conv.try_conv (Conv.rewr_conv del_refl_eq))
   625                         then_conv (Conv.try_conv (Conv.rewr_conv del_refl_eq))
   625                         then_conv conjunct_assoc_conv)) context
   626                         then_conv conjunct_assoc_conv)) context
   626                     then_conv (HOLogic.Trueprop_conv (HOLogic.eq_conv Conv.all_conv (Collect_conv (fn (_, ctxt) =>
   627                     then_conv (HOLogic.Trueprop_conv (HOLogic.eq_conv Conv.all_conv (Collect_conv (fn (_, ctxt) =>
   627                       Conv.repeat_conv
   628                       Conv.repeat_conv
   634                   CONVERSION
   635                   CONVERSION
   635                     (right_hand_set_comprehension_conv (K
   636                     (right_hand_set_comprehension_conv (K
   636                       (HOLogic.conj_conv
   637                       (HOLogic.conj_conv
   637                         ((HOLogic.eq_conv Conv.all_conv
   638                         ((HOLogic.eq_conv Conv.all_conv
   638                           (rewr_conv' (List.last prems))) then_conv
   639                           (rewr_conv' (List.last prems))) then_conv
   639                           (Conv.rewrs_conv (map (fn th => th RS @{thm Eq_FalseI}) (#distinct info))))
   640                           (Conv.rewrs_conv (map (fn th => th RS @{thm Eq_FalseI}) distincts)))
   640                         Conv.all_conv then_conv
   641                         Conv.all_conv then_conv
   641                         (rewr_conv' @{lemma "(False & P) = False" by simp}))) context then_conv
   642                         (rewr_conv' @{lemma "(False & P) = False" by simp}))) context then_conv
   642                       HOLogic.Trueprop_conv
   643                       HOLogic.Trueprop_conv
   643                         (HOLogic.eq_conv Conv.all_conv
   644                         (HOLogic.eq_conv Conv.all_conv
   644                           (Collect_conv (fn (_, ctxt) =>
   645                           (Collect_conv (fn (_, ctxt) =>
   645                             Conv.repeat_conv
   646                             Conv.repeat_conv
   646                               (Conv.bottom_conv
   647                               (Conv.bottom_conv
   647                                 (K (rewr_conv'
   648                                 (K (rewr_conv'
   648                                   @{lemma "(EX x. P) = P" by simp})) ctxt)) context))) 1) ctxt 1
   649                                   @{lemma "(EX x. P) = P" by simp})) ctxt)) context))) 1) ctxt 1
   649                 THEN rtac set_Nil_I 1)) (#case_rewrites info))
   650                 THEN rtac set_Nil_I 1)) case_thms)
   650           end
   651           end
   651     fun make_inner_eqs bound_vs Tis eqs t =
   652     fun make_inner_eqs bound_vs Tis eqs t =
   652       (case dest_case t of
   653       (case dest_case t of
   653         SOME (x, T, i, cont) =>
   654         SOME (x, T, i, cont, constr_name) =>
   654           let
   655           let
   655             val (vs, body) = strip_abs (Envir.eta_long (map snd bound_vs) cont)
   656             val (vs, body) = strip_abs (Envir.eta_long (map snd bound_vs) cont)
   656             val x' = incr_boundvars (length vs) x
   657             val x' = incr_boundvars (length vs) x
   657             val eqs' = map (incr_boundvars (length vs)) eqs
   658             val eqs' = map (incr_boundvars (length vs)) eqs
   658             val (constr_name, _) = nth (the (Datatype.get_constrs thy (fst (dest_Type T)))) i
       
   659             val constr_t =
   659             val constr_t =
   660               list_comb
   660               list_comb
   661                 (Const (constr_name, map snd vs ---> T), map Bound (((length vs) - 1) downto 0))
   661                 (Const (constr_name, map snd vs ---> T), map Bound (((length vs) - 1) downto 0))
   662             val constr_eq = Const (@{const_name HOL.eq}, T --> T --> @{typ bool}) $ constr_t $ x'
   662             val constr_eq = Const (@{const_name HOL.eq}, T --> T --> @{typ bool}) $ constr_t $ x'
   663           in
   663           in