src/Doc/Datatypes/Datatypes.thy
changeset 63680 6e1e8b5abbfa
parent 63669 256fc20716f2
child 64939 c8626f7fae06
equal deleted inserted replaced
63679:dc311d55ad8f 63680:6e1e8b5abbfa
    76 allow infinite paths. Orthogonally, the nodes in the first and third types have
    76 allow infinite paths. Orthogonally, the nodes in the first and third types have
    77 finitely many direct subtrees, whereas those of the second and fourth may have
    77 finitely many direct subtrees, whereas those of the second and fourth may have
    78 infinite branching.
    78 infinite branching.
    79 
    79 
    80 The package is part of @{theory Main}. Additional functionality is provided by
    80 The package is part of @{theory Main}. Additional functionality is provided by
    81 the theory @{file "~~/src/HOL/Library/BNF_Axiomatization.thy"}.
    81 the theory \<^file>\<open>~~/src/HOL/Library/BNF_Axiomatization.thy\<close>.
    82 
    82 
    83 The package, like its predecessor, fully adheres to the LCF philosophy
    83 The package, like its predecessor, fully adheres to the LCF philosophy
    84 @{cite mgordon79}: The characteristic theorems associated with the specified
    84 @{cite mgordon79}: The characteristic theorems associated with the specified
    85 (co)datatypes are derived rather than introduced axiomatically.%
    85 (co)datatypes are derived rather than introduced axiomatically.%
    86 \footnote{However, some of the
    86 \footnote{However, some of the
   161   \label{ssec:datatype-introductory-examples}\<close>
   161   \label{ssec:datatype-introductory-examples}\<close>
   162 
   162 
   163 text \<open>
   163 text \<open>
   164 Datatypes are illustrated through concrete examples featuring different flavors
   164 Datatypes are illustrated through concrete examples featuring different flavors
   165 of recursion. More examples can be found in the directory
   165 of recursion. More examples can be found in the directory
   166 @{dir "~~/src/HOL/Datatype_Examples"}.
   166 \<^dir>\<open>~~/src/HOL/Datatype_Examples\<close>.
   167 \<close>
   167 \<close>
   168 
   168 
   169 
   169 
   170 subsubsection \<open>Nonrecursive Types
   170 subsubsection \<open>Nonrecursive Types
   171   \label{sssec:datatype-nonrecursive-types}\<close>
   171   \label{sssec:datatype-nonrecursive-types}\<close>
  1136 
  1136 
  1137 subsubsection \<open>\textit{countable_datatype}
  1137 subsubsection \<open>\textit{countable_datatype}
  1138   \label{sssec:datatype-compat}\<close>
  1138   \label{sssec:datatype-compat}\<close>
  1139 
  1139 
  1140 text \<open>
  1140 text \<open>
  1141 The theory @{file "~~/src/HOL/Library/Countable.thy"} provides a
  1141 The theory \<^file>\<open>~~/src/HOL/Library/Countable.thy\<close> provides a
  1142 proof method called @{method countable_datatype} that can be used to prove the
  1142 proof method called @{method countable_datatype} that can be used to prove the
  1143 countability of many datatypes, building on the countability of the types
  1143 countability of many datatypes, building on the countability of the types
  1144 appearing in their definitions and of any type arguments. For example:
  1144 appearing in their definitions and of any type arguments. For example:
  1145 \<close>
  1145 \<close>
  1146 
  1146 
  1216 @{text "[where \<dots>]"} attribute. The solution is to use the more robust
  1216 @{text "[where \<dots>]"} attribute. The solution is to use the more robust
  1217 @{text "[of \<dots>]"} syntax.
  1217 @{text "[of \<dots>]"} syntax.
  1218 \end{itemize}
  1218 \end{itemize}
  1219 
  1219 
  1220 The old command is still available as \keyw{old_datatype} in theory
  1220 The old command is still available as \keyw{old_datatype} in theory
  1221 @{file "~~/src/HOL/Library/Old_Datatype.thy"}. However, there is no general
  1221 \<^file>\<open>~~/src/HOL/Library/Old_Datatype.thy\<close>. However, there is no general
  1222 way to register old-style datatypes as new-style datatypes. If the objective
  1222 way to register old-style datatypes as new-style datatypes. If the objective
  1223 is to define new-style datatypes with nested recursion through old-style
  1223 is to define new-style datatypes with nested recursion through old-style
  1224 datatypes, the old-style datatypes can be registered as a BNF
  1224 datatypes, the old-style datatypes can be registered as a BNF
  1225 (Section~\ref{sec:registering-bounded-natural-functors}). If the objective is
  1225 (Section~\ref{sec:registering-bounded-natural-functors}). If the objective is
  1226 to derive discriminators and selectors, this can be achieved using
  1226 to derive discriminators and selectors, this can be achieved using
  1245   \label{ssec:primrec-introductory-examples}\<close>
  1245   \label{ssec:primrec-introductory-examples}\<close>
  1246 
  1246 
  1247 text \<open>
  1247 text \<open>
  1248 Primitive recursion is illustrated through concrete examples based on the
  1248 Primitive recursion is illustrated through concrete examples based on the
  1249 datatypes defined in Section~\ref{ssec:datatype-introductory-examples}. More
  1249 datatypes defined in Section~\ref{ssec:datatype-introductory-examples}. More
  1250 examples can be found in the directory @{dir "~~/src/HOL/Datatype_Examples"}.
  1250 examples can be found in the directory \<^dir>\<open>~~/src/HOL/Datatype_Examples\<close>.
  1251 \<close>
  1251 \<close>
  1252 
  1252 
  1253 
  1253 
  1254 subsubsection \<open>Nonrecursive Types
  1254 subsubsection \<open>Nonrecursive Types
  1255   \label{sssec:primrec-nonrecursive-types}\<close>
  1255   \label{sssec:primrec-nonrecursive-types}\<close>
  1318 text \<open>
  1318 text \<open>
  1319 \noindent
  1319 \noindent
  1320 Pattern matching is only available for the argument on which the recursion takes
  1320 Pattern matching is only available for the argument on which the recursion takes
  1321 place. Fortunately, it is easy to generate pattern-maching equations using the
  1321 place. Fortunately, it is easy to generate pattern-maching equations using the
  1322 @{command simps_of_case} command provided by the theory
  1322 @{command simps_of_case} command provided by the theory
  1323 @{file "~~/src/HOL/Library/Simps_Case_Conv.thy"}.
  1323 \<^file>\<open>~~/src/HOL/Library/Simps_Case_Conv.thy\<close>.
  1324 \<close>
  1324 \<close>
  1325 
  1325 
  1326     simps_of_case at_simps_alt: at.simps
  1326     simps_of_case at_simps_alt: at.simps
  1327 
  1327 
  1328 text \<open>
  1328 text \<open>
  1758 
  1758 
  1759 text \<open>
  1759 text \<open>
  1760 Codatatypes can be specified using the @{command codatatype} command. The
  1760 Codatatypes can be specified using the @{command codatatype} command. The
  1761 command is first illustrated through concrete examples featuring different
  1761 command is first illustrated through concrete examples featuring different
  1762 flavors of corecursion. More examples can be found in the directory
  1762 flavors of corecursion. More examples can be found in the directory
  1763 @{dir "~~/src/HOL/Datatype_Examples"}. The \emph{Archive of Formal Proofs} also
  1763 \<^dir>\<open>~~/src/HOL/Datatype_Examples\<close>. The \emph{Archive of Formal Proofs} also
  1764 includes some useful codatatypes, notably for lazy lists @{cite
  1764 includes some useful codatatypes, notably for lazy lists @{cite
  1765 "lochbihler-2010"}.
  1765 "lochbihler-2010"}.
  1766 \<close>
  1766 \<close>
  1767 
  1767 
  1768 
  1768 
  2036 \keyw{corec} and \keyw{corecursive} commands, and techniques based on domains
  2036 \keyw{corec} and \keyw{corecursive} commands, and techniques based on domains
  2037 and topologies @{cite "lochbihler-hoelzl-2014"}. In this tutorial, the focus is
  2037 and topologies @{cite "lochbihler-hoelzl-2014"}. In this tutorial, the focus is
  2038 on @{command primcorec} and @{command primcorecursive}; \keyw{corec} and
  2038 on @{command primcorec} and @{command primcorecursive}; \keyw{corec} and
  2039 \keyw{corecursive} are described in a separate tutorial
  2039 \keyw{corecursive} are described in a separate tutorial
  2040 @{cite "isabelle-corec"}. More examples can be found in the directories
  2040 @{cite "isabelle-corec"}. More examples can be found in the directories
  2041 @{dir "~~/src/HOL/Datatype_Examples"} and @{dir "~~/src/HOL/Corec_Examples"}.
  2041 \<^dir>\<open>~~/src/HOL/Datatype_Examples\<close> and \<^dir>\<open>~~/src/HOL/Corec_Examples\<close>.
  2042 
  2042 
  2043 Whereas recursive functions consume datatypes one constructor at a time,
  2043 Whereas recursive functions consume datatypes one constructor at a time,
  2044 corecursive functions construct codatatypes one constructor at a time.
  2044 corecursive functions construct codatatypes one constructor at a time.
  2045 Partly reflecting a lack of agreement among proponents of coalgebraic methods,
  2045 Partly reflecting a lack of agreement among proponents of coalgebraic methods,
  2046 Isabelle supports three competing syntaxes for specifying a function $f$:
  2046 Isabelle supports three competing syntaxes for specifying a function $f$:
  2080   \label{ssec:primcorec-introductory-examples}\<close>
  2080   \label{ssec:primcorec-introductory-examples}\<close>
  2081 
  2081 
  2082 text \<open>
  2082 text \<open>
  2083 Primitive corecursion is illustrated through concrete examples based on the
  2083 Primitive corecursion is illustrated through concrete examples based on the
  2084 codatatypes defined in Section~\ref{ssec:codatatype-introductory-examples}. More
  2084 codatatypes defined in Section~\ref{ssec:codatatype-introductory-examples}. More
  2085 examples can be found in the directory @{dir "~~/src/HOL/Datatype_Examples"}.
  2085 examples can be found in the directory \<^dir>\<open>~~/src/HOL/Datatype_Examples\<close>.
  2086 The code view is favored in the examples below. Sections
  2086 The code view is favored in the examples below. Sections
  2087 \ref{ssec:primrec-constructor-view} and \ref{ssec:primrec-destructor-view}
  2087 \ref{ssec:primrec-constructor-view} and \ref{ssec:primrec-destructor-view}
  2088 present the same examples expressed using the constructor and destructor views.
  2088 present the same examples expressed using the constructor and destructor views.
  2089 \<close>
  2089 \<close>
  2090 
  2090 
  2141 For technical reasons, @{text "case"}--@{text "of"} is only supported for
  2141 For technical reasons, @{text "case"}--@{text "of"} is only supported for
  2142 case distinctions on (co)datatypes that provide discriminators and selectors.
  2142 case distinctions on (co)datatypes that provide discriminators and selectors.
  2143 
  2143 
  2144 Pattern matching is not supported by @{command primcorec}. Fortunately, it is
  2144 Pattern matching is not supported by @{command primcorec}. Fortunately, it is
  2145 easy to generate pattern-maching equations using the @{command simps_of_case}
  2145 easy to generate pattern-maching equations using the @{command simps_of_case}
  2146 command provided by the theory @{file "~~/src/HOL/Library/Simps_Case_Conv.thy"}.
  2146 command provided by the theory \<^file>\<open>~~/src/HOL/Library/Simps_Case_Conv.thy\<close>.
  2147 \<close>
  2147 \<close>
  2148 
  2148 
  2149     simps_of_case lapp_simps: lapp.code
  2149     simps_of_case lapp_simps: lapp.code
  2150 
  2150 
  2151 text \<open>
  2151 text \<open>
  2774   \label{ssec:bnf-introductory-examples}\<close>
  2774   \label{ssec:bnf-introductory-examples}\<close>
  2775 
  2775 
  2776 text \<open>
  2776 text \<open>
  2777 The example below shows how to register a type as a BNF using the @{command bnf}
  2777 The example below shows how to register a type as a BNF using the @{command bnf}
  2778 command. Some of the proof obligations are best viewed with the theory
  2778 command. Some of the proof obligations are best viewed with the theory
  2779 @{file "~~/src/HOL/Library/Cardinal_Notations.thy"} imported.
  2779 \<^file>\<open>~~/src/HOL/Library/Cardinal_Notations.thy\<close> imported.
  2780 
  2780 
  2781 The type is simply a copy of the function space @{typ "'d \<Rightarrow> 'a"}, where @{typ 'a}
  2781 The type is simply a copy of the function space @{typ "'d \<Rightarrow> 'a"}, where @{typ 'a}
  2782 is live and @{typ 'd} is dead. We introduce it together with its map function,
  2782 is live and @{typ 'd} is dead. We introduce it together with its map function,
  2783 set function, predicator, and relator.
  2783 set function, predicator, and relator.
  2784 \<close>
  2784 \<close>
  2873 Using \keyw{print_theorems} and @{command print_bnfs}, we can contemplate and
  2873 Using \keyw{print_theorems} and @{command print_bnfs}, we can contemplate and
  2874 show the world what we have achieved.
  2874 show the world what we have achieved.
  2875 
  2875 
  2876 This particular example does not need any nonemptiness witness, because the
  2876 This particular example does not need any nonemptiness witness, because the
  2877 one generated by default is good enough, but in general this would be
  2877 one generated by default is good enough, but in general this would be
  2878 necessary. See @{file "~~/src/HOL/Basic_BNFs.thy"},
  2878 necessary. See \<^file>\<open>~~/src/HOL/Basic_BNFs.thy\<close>,
  2879 @{file "~~/src/HOL/Library/Countable_Set_Type.thy"},
  2879 \<^file>\<open>~~/src/HOL/Library/Countable_Set_Type.thy\<close>,
  2880 @{file "~~/src/HOL/Library/FSet.thy"}, and
  2880 \<^file>\<open>~~/src/HOL/Library/FSet.thy\<close>, and
  2881 @{file "~~/src/HOL/Library/Multiset.thy"} for further examples of BNF
  2881 \<^file>\<open>~~/src/HOL/Library/Multiset.thy\<close> for further examples of BNF
  2882 registration, some of which feature custom witnesses.
  2882 registration, some of which feature custom witnesses.
  2883 
  2883 
  2884 For many typedefs, lifting the BNF structure from the raw type to the abstract
  2884 For many typedefs, lifting the BNF structure from the raw type to the abstract
  2885 type can be done uniformly. This is the task of the @{command lift_bnf} command.
  2885 type can be done uniformly. This is the task of the @{command lift_bnf} command.
  2886 Using @{command lift_bnf}, the above registration of @{typ "('d, 'a) fn"} as a
  2886 Using @{command lift_bnf}, the above registration of @{typ "('d, 'a) fn"} as a
  3105 is identical to the left-hand side of a @{command datatype} or
  3105 is identical to the left-hand side of a @{command datatype} or
  3106 @{command codatatype} definition.
  3106 @{command codatatype} definition.
  3107 
  3107 
  3108 The command is useful to reason abstractly about BNFs. The axioms are safe
  3108 The command is useful to reason abstractly about BNFs. The axioms are safe
  3109 because there exist BNFs of arbitrary large arities. Applications must import
  3109 because there exist BNFs of arbitrary large arities. Applications must import
  3110 the @{file "~~/src/HOL/Library/BNF_Axiomatization.thy"} theory
  3110 the \<^file>\<open>~~/src/HOL/Library/BNF_Axiomatization.thy\<close> theory
  3111 to use this functionality.
  3111 to use this functionality.
  3112 \<close>
  3112 \<close>
  3113 
  3113 
  3114 
  3114 
  3115 subsubsection \<open>\keyw{print_bnfs}
  3115 subsubsection \<open>\keyw{print_bnfs}
  3208 
  3208 
  3209 \medskip
  3209 \medskip
  3210 
  3210 
  3211 \noindent
  3211 \noindent
  3212 The @{command simps_of_case} command provided by theory
  3212 The @{command simps_of_case} command provided by theory
  3213 @{file "~~/src/HOL/Library/Simps_Case_Conv.thy"} converts a single equation with
  3213 \<^file>\<open>~~/src/HOL/Library/Simps_Case_Conv.thy\<close> converts a single equation with
  3214 a complex case expression on the right-hand side into a set of pattern-matching
  3214 a complex case expression on the right-hand side into a set of pattern-matching
  3215 equations. For example,
  3215 equations. For example,
  3216 \<close>
  3216 \<close>
  3217 
  3217 
  3218 (*<*)
  3218 (*<*)
  3247 
  3247 
  3248 \medskip
  3248 \medskip
  3249 
  3249 
  3250 \noindent
  3250 \noindent
  3251 The \keyw{case_of_simps} command provided by theory
  3251 The \keyw{case_of_simps} command provided by theory
  3252 @{file "~~/src/HOL/Library/Simps_Case_Conv.thy"} converts a set of
  3252 \<^file>\<open>~~/src/HOL/Library/Simps_Case_Conv.thy\<close> converts a set of
  3253 pattern-matching equations into single equation with a complex case expression
  3253 pattern-matching equations into single equation with a complex case expression
  3254 on the right-hand side (cf.\ @{command simps_of_case}). For example,
  3254 on the right-hand side (cf.\ @{command simps_of_case}). For example,
  3255 \<close>
  3255 \<close>
  3256 
  3256 
  3257     case_of_simps lapp_case: lapp_simps
  3257     case_of_simps lapp_case: lapp_simps
  3384 @{text "'a\<^sub>1, \<dots>, 'a\<^sub>m"}, by default @{text u} values are given a size of 0. This
  3384 @{text "'a\<^sub>1, \<dots>, 'a\<^sub>m"}, by default @{text u} values are given a size of 0. This
  3385 can be improved upon by registering a custom size function of type
  3385 can be improved upon by registering a custom size function of type
  3386 @{text "('a\<^sub>1 \<Rightarrow> nat) \<Rightarrow> \<dots> \<Rightarrow> ('a\<^sub>m \<Rightarrow> nat) \<Rightarrow> u \<Rightarrow> nat"} using
  3386 @{text "('a\<^sub>1 \<Rightarrow> nat) \<Rightarrow> \<dots> \<Rightarrow> ('a\<^sub>m \<Rightarrow> nat) \<Rightarrow> u \<Rightarrow> nat"} using
  3387 the ML function @{ML BNF_LFP_Size.register_size} or
  3387 the ML function @{ML BNF_LFP_Size.register_size} or
  3388 @{ML BNF_LFP_Size.register_size_global}. See theory
  3388 @{ML BNF_LFP_Size.register_size_global}. See theory
  3389 @{file "~~/src/HOL/Library/Multiset.thy"} for an example.
  3389 \<^file>\<open>~~/src/HOL/Library/Multiset.thy\<close> for an example.
  3390 \<close>
  3390 \<close>
  3391 
  3391 
  3392 
  3392 
  3393 subsection \<open>Transfer
  3393 subsection \<open>Transfer
  3394   \label{ssec:transfer}\<close>
  3394   \label{ssec:transfer}\<close>