src/HOL/Library/Poly_Mapping.thy
changeset 70045 7b6add80e3a5
parent 70043 350acd367028
child 73655 26a1d66b9077
equal deleted inserted replaced
70044:da5857dbcbb9 70045:7b6add80e3a5
     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.