7 |
7 |
8 theory Poly_Mapping |
8 theory Poly_Mapping |
9 imports Groups_Big_Fun Fun_Lexorder More_List |
9 imports Groups_Big_Fun Fun_Lexorder More_List |
10 begin |
10 begin |
11 |
11 |
12 subsection \<open>Preliminary: auxiliary operations for \qt{almost everywhere zero}\<close> |
12 subsection \<open>Preliminary: auxiliary operations for \emph{almost everywhere zero}\<close> |
13 |
13 |
14 text \<open> |
14 text \<open> |
15 A central notion for polynomials are functions being \qt{almost everywhere zero}. |
15 A central notion for polynomials are functions being \emph{almost everywhere zero}. |
16 For these we provide some auxiliary definitions and lemmas. |
16 For these we provide some auxiliary definitions and lemmas. |
17 \<close> |
17 \<close> |
18 |
18 |
19 lemma finite_mult_not_eq_zero_leftI: |
19 lemma finite_mult_not_eq_zero_leftI: |
20 fixes f :: "'b \<Rightarrow> 'a :: mult_zero" |
20 fixes f :: "'b \<Rightarrow> 'a :: mult_zero" |
256 |
256 |
257 lemma poly_mapping_eq_iff: "a = b \<longleftrightarrow> lookup a = lookup b" |
257 lemma poly_mapping_eq_iff: "a = b \<longleftrightarrow> lookup a = lookup b" |
258 by auto |
258 by auto |
259 |
259 |
260 text \<open> |
260 text \<open> |
261 We model the universe of functions being \qt{almost everywhere zero} |
261 We model the universe of functions being \emph{almost everywhere zero} |
262 by means of a separate type @{typ "('a, 'b) poly_mapping"}. |
262 by means of a separate type @{typ "('a, 'b) poly_mapping"}. |
263 For convenience we provide a suggestive infix syntax which |
263 For convenience we provide a suggestive infix syntax which |
264 is a variant of the usual function space syntax. Conversion between both types |
264 is a variant of the usual function space syntax. Conversion between both types |
265 happens through the morphisms |
265 happens through the morphisms |
266 \begin{quote} |
266 \begin{quote} |
287 text \<open> |
287 text \<open> |
288 @{typ "'a \<Rightarrow>\<^sub>0 'b"} serves distinctive purposes: |
288 @{typ "'a \<Rightarrow>\<^sub>0 'b"} serves distinctive purposes: |
289 \begin{enumerate} |
289 \begin{enumerate} |
290 \item A clever nesting as @{typ "(nat \<Rightarrow>\<^sub>0 nat) \<Rightarrow>\<^sub>0 'a"} |
290 \item A clever nesting as @{typ "(nat \<Rightarrow>\<^sub>0 nat) \<Rightarrow>\<^sub>0 'a"} |
291 later in theory \<open>MPoly\<close> gives a suitable |
291 later in theory \<open>MPoly\<close> gives a suitable |
292 representation type for polynomials \qt{almost for free}: |
292 representation type for polynomials \emph{almost for free}: |
293 Interpreting @{typ "nat \<Rightarrow>\<^sub>0 nat"} as a mapping from variable identifiers |
293 Interpreting @{typ "nat \<Rightarrow>\<^sub>0 nat"} as a mapping from variable identifiers |
294 to exponents yields monomials, and the whole type maps monomials |
294 to exponents yields monomials, and the whole type maps monomials |
295 to coefficients. Lets call this the \emph{ultimate interpretation}. |
295 to coefficients. Lets call this the \emph{ultimate interpretation}. |
296 \item A further more specialised type isomorphic to @{typ "nat \<Rightarrow>\<^sub>0 'a"} |
296 \item A further more specialised type isomorphic to @{typ "nat \<Rightarrow>\<^sub>0 'a"} |
297 is apt to direct implementation using code generation |
297 is apt to direct implementation using code generation |
298 \cite{Haftmann-Nipkow:2010:code}. |
298 \cite{Haftmann-Nipkow:2010:code}. |
299 \end{enumerate} |
299 \end{enumerate} |
300 Note that despite the names \qt{mapping} and \qt{lookup} suggest something |
300 Note that despite the names \emph{mapping} and \emph{lookup} suggest something |
301 implementation-near, it is best to keep @{typ "'a \<Rightarrow>\<^sub>0 'b"} as an abstract |
301 implementation-near, it is best to keep @{typ "'a \<Rightarrow>\<^sub>0 'b"} as an abstract |
302 \emph{algebraic} type |
302 \emph{algebraic} type |
303 providing operations like \qt{addition}, \qt{multiplication} without any notion |
303 providing operations like \emph{addition}, \emph{multiplication} without any notion |
304 of key-order, data structures etc. This implementations-specific notions are |
304 of key-order, data structures etc. This implementations-specific notions are |
305 easily introduced later for particular implementations but do not provide any |
305 easily introduced later for particular implementations but do not provide any |
306 gain for specifying logical properties of polynomials. |
306 gain for specifying logical properties of polynomials. |
307 \<close> |
307 \<close> |
308 |
308 |
317 Isabelle has a rich hierarchy of algebraic type classes, and in such situations |
317 Isabelle has a rich hierarchy of algebraic type classes, and in such situations |
318 of pointwise lifting a typical pattern is to have instantiations for a considerable |
318 of pointwise lifting a typical pattern is to have instantiations for a considerable |
319 number of type classes. |
319 number of type classes. |
320 |
320 |
321 The operations themselves are specified using \<open>lift_definition\<close>, where |
321 The operations themselves are specified using \<open>lift_definition\<close>, where |
322 the proofs of the \qt{almost everywhere zero} property can be significantly involved. |
322 the proofs of the \emph{almost everywhere zero} property can be significantly involved. |
323 |
323 |
324 The @{const lookup} operation is supposed to be usable explicitly (unless in |
324 The @{const lookup} operation is supposed to be usable explicitly (unless in |
325 other situations where the morphisms between types are somehow internal |
325 other situations where the morphisms between types are somehow internal |
326 to the \emph{lifting} package). Hence it is good style to provide explicit rewrite |
326 to the \emph{lifting} package). Hence it is good style to provide explicit rewrite |
327 rules how @{const lookup} acts on operations immediately. |
327 rules how @{const lookup} acts on operations immediately. |