Reading Viktor's post, I found myself provoked by some – in my
opinion – omissions and inaccuracies in his definitions.
He also has a different perspective on how categories apply to
programming and to Haskell in particular, to which I tend to
partially disagree.
Instead of, as I originally intended, just commenting on specific
topics, I set about describing what functors and related concepts are
in category theory, how they map to Haskell, and how they are being
used in that language. The resulting text is longer than I would
like it, but, hopefully, it clarifies the topic with sufficient
detail and so can be useful in some ways to J-ers.
Categories and functors
***********************
A category consists of two kinds of entities: objects and morphisms,
a.k.a. arrows. Each arrow maps one single object to another (in the
same category), and is what we call a function in other contexts.
Arrows can be composed one after another, thus producing new arrows.
The arrows of a category furnish it with structure by relating
its objects to each other. Arrows, in turn, are related through
composition, so the latter plays an important role in respect of
the category's structure.
It is often the case that the objects and arrows of a category come
from some other domain of consideration. However, from the perspective
of the category, neither of them has an internal structure or whatever
properties of their own. Being the domain or codomain of arrows is
the only thing at all that an object can be in its category, and an
arrow is nothing more than a link from one object to another.
A functor is a mapping from one category, A, to another (or sometimes
the same), B. It consists of two maps – one from the objects of A to
those of B, and another from the arrows of A to those of B. Now, we
expect a functor to not just be an arbitrary mapping, but also to
correlate the structure of its domain category (A) to that of the
codomain (B). To this end, the arrow part of the functor, let's call
it Fa, has to obey, for each pair of arrows f and g in A, the identity
Fa (f∘g) ≡ (Fa f) ∘ (Fa g)
which means that the image in B of the composition f∘g in A is
precisely the composition of the images of f and g (the latter
composition taking place in B). Or, shortly put: the image of a
composition is the composition of images. We could also say that
'Fa distributes over ∘', in the same sense that multiplication
distributes over addition in arithmetic.
There is one more property for Fa to obey – it is so simple and
obviously necessary that it is easy to remain unnoticed, but it
has to be stated explicitly: Fa has to also 'distribute' over the
identity arrows: if i(x) is the arrow from x to itself in A, then
Fa i(x) ≡ i(Fa x) ,
where i(Fa x) is the arrow from Fa x to itself.
In the sense of the above two axioms, a functor is a structure-
preserving operation on categories.
Categories and functors in Haskell
**********************************
In Haskell, the concept of a functor is very close to the one in the
category theory. Of course, this is an empty statement unless we know
what in Haskell corresponds to categories, objects, and arrows. So,
first things first.
Think of datatypes as objects of which categories are constructed.
We can imagine one universal category whose objects are all the
datatypes of a programming language (here, Haskell). Correspondingly,
each function is an arrow in this category.
Data structures, such as lists, trees etc., are usually represented
as datatypes. But, in a typed language, one cannot have a data object
that is simply 'a list', there must be specified 'a list of integers'
or similar. So, from each data structure emerges a family of concrete
types with the same organization but different types of elements. It
makes sense to think of such a family as parameterized by its element
type. It is therefore useful to associate with the type family a
function which, given a datatype, produces another type – a member of
the family. In Haskell, this concept is embodied in the so called
'type constructors', or 'tycons' for short.
From a categorial point of view, to each family of types as described
above, there corresponds a category (whose objects are the members of
the family). Thus there are categories of lists, of trees, etc.
The objects of the category of lists are the types of integer-valued,
real-valued, string-valued, etc. lists.
Note that there is a one-to-one correspondence between tyconses and
categories (except the universal category), naturally established
through both being associated with the same family of types.
As any other value, functions are typed, and their types are written
f :: a -> b, meaning that the function f has a domain a and a codomain
b. Because there can be many functions of the same signature a -> b,
there are many arrows between any two objects in any of the categories,
the universal one or the specific.
After all this, what is a functor in Haskell? It is a mapping, in
the above described categorial sense of the word 'functor', from the
universal category of types to any one of the specific categories.
The definition of functor is embodied in the following type class
interface:
class Functor t where
fmap :: (a -> b) -> (t a -> t b)
together with the axioms
fmap id ≡ id
fmap (f . g) ≡ fmap f . fmap g
In the above interface, t represents a dummy tycon for which a
function fmap is defined that has the given signature and satisfies
the axioms. fmap transforms any function into a function whose domain
and codomain are types produced by that constructor. (Given that the
original function's domain and codomain are a and b, fmap produces a
function whose domain and codomain are the types (t a) and (t b).)
In this way, fmap 'adapts' general functions for use within the data
structure represented by the tycon.
E.g., the t can be the tycon of lists which, given a type x, produces
a list with element type x. That t is made an instance of Functor by
trivially defining fmap to be the library function 'map' which, given
a function f, creates a function that transforms a list by applying f
to each of its elements.
A tycon for which fmap exists is often, informally, called a functor.
Strictly speaking, it implements a functor with codomain the tycon's
respective category.
Note that fmap only represents the arrow part of the functor. The
object part is implicit. It must also be stressed that satisfying
the axioms is not (and could not be) automatic – ensuring that they
are valid for a specific implementation of fmap is a programmer's
obligation!
Functors in J?
**************
The observed correspondence between category theory and Haskell can
be summarized in the following table.
category theory Haskell
---------------------------------------------------------------------
category the universal category of types;
specific categories (families of datatypes)
category constructor type constructor
object type
arrow function
composition of arrows composition of functions
definition of functor Functor interface and axioms
as concept
functor axioms-complying implementation of Functor
(associated with a specific tycon)
If we can build a similar table with J in the right column, we can
say that we have an idea what might be a J's version of functors in
general.
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
