Of function instances and abstract syntax
Previous: Proving My Point
Some Haskell classes class Myclass a
admit an instance for functions
instance Myclass a => Myclass (x -> a)
based on the instance for a
.
All of these instances have a few things in common: (1) they implement
the class methods in a straightforward way as mymethod f = \x -> mymethod (f x)
,
and (2) they are polarizing among Haskell practitioners. The sequel is a
case study of why I find such instances compelling and useful.
The dictionary of functions that comprise a Num
instance is roughly
(if you omit abs
and signum
) the signature of what math folk call a
commutative ring.
A commutative ring \(R\) is a set (or type) on which associative,
commutative operations \(+\) and \(\cdot\) are defined, a unary operation \(-\) is
defined that takes a ring element to its \(+\) inverse, \(\cdot\) distributes
over \(+\), there is an element called \(0\) that is an identity for \(+\),
there is an element called \(1\) that is an identity for \(\cdot\), and \(0\) and
\(1\) are distinct. This gives us our +
, *
, and negate
functions in
Haskell’s Num
.
For any commutative ring \(R\), it is possible to define one (and only one) function \(i\) from the integers to \(R\) with the following special properties:
-
\(i\) distributes over the usual \(+\) and \(\cdot\) of the integers, yielding the \(+\) and \(\cdot\) of \(R\) when it does, i.e.
\[\begin{align*} i(x + y) &= i(x) + i(y) \\ i(x \cdot y) &= i(x) \cdot i(y) \end{align*}\]where \(+\) and \(\cdot\) on the left hand side refer to the usual operations defined for integers, but \(+\) and \(\cdot\) on the right hand side refer to the ring operations defined for \(R\).
-
\(i(0)\) is the \(0\) of \(R\), and \(i(1)\) is the \(1\) of \(R\).
Facts 1 and 2 tell us that every commutative ring (abbreviated to just
ring for the remainder of this discussion) has an image of the
integers inside of it. This function \(i\) is analogous to our
fromInteger
function in Haskell’s Num
. At the same time, implementing
fromInteger
for a Num
instances implicitly defines the \(0\) and \(1\)
of our ring vis a vis fromInteger 0
and fromInteger 1
.
Obviously \(\mathbb{Z}\), the set of all integers, is a ring. In a sense, \(\mathbb{Z}\) is the most prototypical ring. But there are many other rings, some exotic. For example, Take any set \(X\), and form the set \(\mathop{\mathrm{Pow}}(X)\) consisting of all subsets of \(X\). Recall \(\cap\) is the usual intersection of sets, \(\cup\) is the usual union of sets, and \(\setminus\) is the usual difference of sets (i.e., \(E_1 \setminus E_2 = \left\{ x \mid x \in E_1 \text{ and } x \notin E_2 \right\}\)). Define \(\mathop{\Delta}\) by \(E_1 \mathop{\Delta} E_2 = (E_1 \cup E_2) \setminus (E_1 \cap E_2)\). Then, perhaps surprisingly, \(\mathop{\mathrm{Pow}}(X)\) is a ring using \(\mathop{\Delta}\) as \(+\), \(\cap\) as \(\ast\), and the identity function as \(-\) (i.e. every set is its own \(\Delta\) inverse).
If \(R_1\) and \(R_2\) are rings, then \(R_1 \times R_2\) (the set of ordered pairs) is a ring using \((x_1, x_2) + (y_1, y_2) = (x_1 + y_1, x_2 + y_2)\) and \((x_1, x_2) \cdot (y_1, y_2) = (x_1 \cdot y_1, x_2 \cdot y_2)\). Towards our main goal, if \(R\) is a ring and if \(X\) is any arbitrary set, then the set of all functions from \(X\) to \(R\) is a ring using \(f + g = x \mapsto f(x) + g(x)\) and \(f \cdot g = x \mapsto f(x) \cdot g(x)\).
Finally, the polynomials: if \(X\) is any set, define the polynomials in \(X\), which we’ll write as \(P(X)\), as the set of all formal expressions of the form
\[n_1 x_{1,1} x_{1,2} ... x_{1,k_1} + n_2 x_{2,1} x_ {2,2} ... x_ {2,k_ 2} + ... + n_m x_{m,1} x_{m,2} ... x_{m,k_m}\]where the \(n_i\) are integers, the \(k_i\) and \(m\) are non-negative integers, and the \(x_{i,j}\) are elements of \(X\).
Put more constructively:
-
each individual integer is a polynomial in \(X\),
-
a string of element of \(X\) is a polynomial in \(X\),
-
if \(p_1\) is a polynomial in \(X\) of Form 1 and \(p_2\) is a polynomial in \(X\) of Form 2, then the juxtaposition \(p_1 p_2\) is a polynomial in \(X\), and
-
if \(p_1\) and \(p_2\) are a polynomials in \(X\), then the formal expression \(p_1 + p_2\) is a polynomial in \(X\).
We could directly encode this as a Haskell datatype as follows.
Doing so, we notice that Form3
subsumes Form1
and Form2
, so we
will work with a simplified definition.
Traditionally elements of \(X\) are called the variables, generators, or indeterminates of \(P(X)\), so you will often see \(P(X)\) referred to as the polynomials generated by \(X\) or as the polynomials with indeterminates in \(X\). Elements of \(X\) may be lifted into \(P(X)\) (i.e., thought of as elements of \(P(X)\)) in light of Form 2.
\(P(X)\) forms a ring, independent of (e.g. ignoring) any existing ring structure on \(X\) itself.
Reasonable sets to use for \(X\) include any singleton set, from which arise polynomials in one variable, any pair set, from which arise polynomials in two variables, etc. You may derive the set of polynomials in infinitely-many variables by using \(\mathbb{Z}\) for \(X\), but you must take care when you do: polynomials of Form 1 inherit the ring structure of the integers, but polynomials of Form 2 are merely abstract symbols with no ring structure other than that of \(P(\mathbb{Z})\) defined above. Thus, \(P(\mathbb{Z})\) contains two distinct copies of \(\mathbb{Z}\) with different algebraic properties, and it’s up to you to always be cognizant whether an integer was lifted into \(P(\mathbb{Z})\) using Form 1 or using Form 2. Because of this possibility for confusion, it is often more convenient to use the set of character strings as \(X\) to give rise to the ring of polynomials in infinitely-many variables, and you get the added benefit of being able to name variables. Using the empty set for \(X\) gives a ring that is indistinguishable (from the point of view of ring theory) from \(\mathbb{Z}\).
In computery terms, the polynomials in \(X\) are the “ring expressions”, with variables denoted by elements of \(X\). They are the abstract syntax trees of (commutative) ring theory. That is, the polynomials are the expressions that “make sense” and can be interpreted in any ring \(A\), once you throw in a dictionary that assigns an element of \(A\) to each element of \(X\). This framing suggests a deep fact that we’ll discuss next.
Given a set \(X\) and a ring \(A\), we may define the evaluation map of \(X\) to \(A\) that takes a dictionary from \(X\) to \(A\) and a polynomial in \(X\) and determines a value of \(A\) by first substituting values of \(A\) for elements of \(X\) as they appear in the polynomial and then reducing the polynomial according to the ring operations of \(A\) (treating juxtaposition as \(\cdot\) and treating the formal \(+\) exactly as the notation suggests).
Now, remember that at its core, a function from \(X\) to \(A\) is simply a
selection of \(X\)-many elements of \(A\). For example, defining a function
from a one-element set to the set of integers is equivalent to merely
picking an integer. Defining a function from a two-element set to the
set of character strings is equivalent to selecting two particular character
strings (in a particular order). In this sense, we can think of a function \(X\) to \(A\)
as a substitution assignment of values in \(A\) to the indeterminates of
\(P(X)\). Thus, an element of \(P(X)\) is interpreted as a function
on \(A\) with \(X\)-many
variables (recovering fully the classical notion of a polynomial as
being one of those familiar functions from high-school Math). Thus, the
polynomials are the functions that can be defined wholly in terms of the
rings operations, and thus may be applied in any ring. This fact,
encoded above as evalPExpr
, is the essential property of polynomials
from which all of their other properties derive.
It took us quite a lot of work to get here, between the definition of
the datatype PExpr
and its Ring
instance, not to mention the
definition of evalPExpr
. It would be nice if there were an easier way
to reach the light at the end of the tunnel. Notice what happens when we
rearrange the arguments and constraint on evalPExpr
, though.
My hope is that this reminds you of a comment I made above. To paraphrase and summarize the above discussion:
The polynomials with indeterminates in \(X\) are exactly the functions of \(X\)-many variables that make sense in any ring.
Now look at the signature. The (x -> a) -> a
is a function on a
with x
-many variables, where the x -> a
argument is thought of as a
dictionary selecting x
-many elements of a
to substitute into the
function. The forall a. Ring a =>
indicates that this function makes
sense in any Ring
. The type forall a. Ring a => (x -> a) -> a)
is in
fact the ring of polynomials generated by x
in disguise.
Lifting \(X\) values into \(P(X)\) is merely function application.
The evaluation map, the map that promotes an arbitrary \(X\) to \(A\) function into a \(P(X)\) to \(A\) function, is also just application.
And the ring structure on Polynomial x
(i.e., the Ring
instance) is
the familiar Ring
instance for functions.
My claim is that the ring Polynomial x
is indistinguishable (from the
point of view or ring theory) from the ring PExpr x
. To convince you
of this, I need to define a function from Polynomial x
to PExpr x
that (1) is invertible and that (2) distributes over the ring
operations. These two facts together would mean that any ring-theoretic
statement of fact you could make about PExpr x
would have a
corresponding statement of fact about Polynomial x
, and vice versa.
Here’s that function.
Doing the easy job first, we’ll establish that toExpr
distributes over
the ring operations.
Now, we need to see that toExpr
is invertible. To do that, we’ll
define a function going the other way, and then show that they cancel
each other.
Using the definitions of the Ring
operations defined in the instance
for PExpr x
, we’ll see that toExpr . fromExpr = id
.
So toExpr . fromExpr
fixes Form3
expressions. Likewise for Form4
expressions. For this, we use induction. Suppose that expr1
and
expr2
are in PExpr x
and that (toExpr . fromExpr) expr1 = expr1
and (toExpr . fromExpr) expr2 = expr2
.
We’ve left to show that fromExpr . toExpr = id
. This is highly
technical and only true if we assume termination. We would proceed using
induction on the set of all functions of the form
Ring a => (x -> a) -> a
. We know that any (terminating) function of
that form can only apply the dictionary to inhabitants of x
and use
the Ring
methods, so we’d have base cases \dict -> fromInteger n
and \dict -> dict x
, and we have
induction cases \dict -> f dict + g dict
, \dict -> f dict * g dict
,
and \dict -> negate (f dict)
. We’d show the base cases all satisfy
(fromExpr . toExpr) p = p
, and we’d show that each induction case
satisfies (fromExpr . toExpr) p = p
when we assume the hypotheses
(fromExpr . toExpr) f = f
and (fromExpr . toExpr) g = g
. We’ll spare
the details, but assuming this work is done, we will have accomplished
our goal of showing that Polynomial x
and PExpr x
are
indistinguishable from the point of view of ring theory.
Now some philosophy. The Ring
instance for the function type X -> A
defines the ring operations for functions in terms of the operations on
the type A
. In a sense, X -> A
inherits its ring structure (its
Ring
instance) from the ring structure of A
. An element of
Polynomial x
, that is, a function Ring a => (x -> a) -> a
, is
polymorphic in a
. Any ring may be slotted in for a
, and the
polynomial can be evaluated at that type. Yet Ring a => (x -> a) -> a
is
a function type; it inherits its ring structure from the target ring
a
, which–again–can be any ring. In a sense, Polynomial x
inherits
its ring structure from every ring.
Recall that we earlier said that the ring of integers is the most-
prototypical ring. Every other ring contains a projection of the ring of
integers, witnessed by its fromInteger
implementation. The polynomial
rings, inheriting their ring structure from every ring, are the
counterpoint to the integers’ maximal prototypicality. By inheriting the
ring structure of every ring, the polynomial rings are the most general
rings.
There is a way to make this notion of maximal generality mathematically
precise. Direct your attention to the signature of evalMap
.
I’m very deliberate about the choice of name here. It should remind you of a common Haskell function you’re hopefully familiar with.
Suspending legitimate concerns about termination and infinite lists,
Haskell’s []
functor is commonly thought of as the free monoid
construction. What does that mean? It means that []
is a factory that
produces free monoids. Explicitly, it means that the type [()]
is the
free monoid on one generator (a.k.a. “in one variable”), the type
[Either () ()]
is the free monoid on two generators (a.k.a. “in two variables”). The type [x]
is the free monoid generated by x
(i.e., monoid expressions with indeterminates in x
). Elements of the free monoid generated by x
are abstract monoid-syntax trees, using the elements of x
as variables. foldMap
is the function that allows us to interpret the abstract syntax, promoting a dictionary of assignments x
-> a
to a function[x] -> a
. This explanation of what it means to be a free monoid should sound familiar to you, because it’s analogous to the discussion we had earlier about polynomials, whereby our intuitive notion that the polynomials Polynomial
x
are the x
-variable functions that make sense in any ring is made precise. The polynomial ring Polynomial
x
is the free (commutative) ring generated by x
, in the same sense that the list type [x]
is the free monoid generated by x
.
Summary:
-
Types that are instances of Haskell’s
Num
class are analogous to (commutative) rings. -
The ring of integers is the most-prototypical ring. Every ring contains an image of the integers.
-
If \(A\) is a ring and if \(X\) is any set, then the set of functions \(X \to A\) is a ring in a non-arbitrary way, in that the ring operations on functions are defined in terms of the ring operations on \(A\). \(X \to A\) inherits its ring structure from \(A\).
-
A polynomial with indeterminates in \(X\) is an \(X\)-variable function that makes sense in any ring. In Haskell terms, that is precisely a polymorphic function with a
Ring
(orNum
) constraint. Equivalently, we can think of polynomials as ring expressions, abstract syntax built from the ring operations. -
The polynomials in \(X\) is a ring in a non-arbitrary way, because the polynomials are functions into a ring (really, functions into any ring), and functions inherit the ring structure of their target ring.
-
Counterpoint to the role the integers play as the most-prototypical ring, The polynomial rings are the most-general rings. The polynomials are functions into any target ring, so the ring of polynomials inherit the ring structure of every ring. Made precise, this is the statement that the polynomial rings are the free (commutative) rings.
Previous: Proving My Point