[Haskell-beginners] Category Theory
Paul Higham
polygame at mac.com
Sat Jun 26 21:51:48 EDT 2010
I am also on a similar quest. Specifically, I want to understand the
connection between the notion of monad as defined in category theory
and the application of this concept to functional programming. Even
more specifically I want to grok how monads provide an elegant
solution to the problem of requiring side effects in a programming
style that expressly forbids them. But anyway with my very limited
understanding of these things I'll take a crack at some of your
questions below.
::paul
On Jun 24, 2010, at 3:33 AM, Matt Andrew wrote:
> Hi all,
>
> I have spend some time over the last couple of days trying to get my
> head around category theory, in order to understand concepts like
> monads a little better, in order to understand Haskell a little
> better =) I have grasped, at least to a degree, the basic concepts
> of 'category,' 'functor' and 'natural transformation' but I am still
> fuzzy on a few specifics and had a couple of questions. I'm doing
> this for self-study and have no one to ask these questions of and so
> thought I'd ask them here.
>
> My first question is this: where are functors understood to 'live,'
> or exist? They operate on categories, are they therefore understood
> to exist outside of the categories they operate on? (I understand
> that functors can form a category themselves, but I'm asking this
> question in relation to the categories they operate on. Are they
> inside or outside of them?)
In category theory a functor exists between two categories in much the
same way that a function exists between two sets. If functors
belonged to a category (as in 'inside' the category) then which
category would they belong to? For example, one of my favourite
functors is the forgetful functor (I can really identify with that
property :) ) that leaves behind some of the structure of the source
object when it picks up the target. Think of a vector space
forgetting its addition and scalar multiplication and becoming just a
set. Such a functor does not rightly 'belong' to the category of
vector spaces because its purpose is to destroy what it means to be a
vector space, and it doesn't belong to the category of sets because
if you are a set why would you be expected to know what it was you
forgot in order to get there when you were already there all along?
>
> In other words when I define a functor in Haskell, are the pair of
> functions 'fmap,' and whatever unary type constructor is defined
> along with it, then part of the morphisms of the Haskell category?
> Or are they outside of the Haskell category (where the Haskell
> category I've seen defined in the articles I've read is one where
> its objects are types and its morphisms functions on those types)?
>
> This leads me to my next question. It seems that all functors in
> Haskell (or at least all members of the functor typeclass) are
> covalent endofunctors. Does this mean that whenever a new functor is
> defined in Haskell, that the Haskell category (H) grows to
> accomodate the effects of that functor? In other words, for any
> covalent endofunctor F : H -> H, do H's morphisms then grow to
> include F(f) and objects to include F(a), where a is any object in H
> and f is any morphism in H?
Again in classical category theory all the objects and morphisms exist
independently of any newly identified functor, so from that view the
answer is 'no', for F to be a functor on H then for all objects a and
morphisms f in H, F(a) and F(f) must already exist in H or the functor
could not have been defined. However, the putative existence of an
object in the Haskell category does not mean that there is an
implementation of it. Note that there are infinitely many integers
that have never been written down, but mathematicians still believe
they exist!
> I have been working off the assumption that the answer to my last
> question is 'yes.' The reason for this is natural transformations.
> Where functors seem to be able to be 'outside' of the categories
> they operate on (whether they are in fact 'outside' or not is my
> first question), natural transformations appear to have to be
> 'inside.' My understanding of the theory is that a natural
> transformation is a collection of morphisms in the target category
> of two parallel functors (where such morphisms operate on the
> functors and meet some specific properties). Surely the only way
> such a collection of morphisms would make sense would be if the
> objects they map to/from (i.e. the structures imposed by the two
> functors) were part of that category also?
Is it possible that there is some confusion coming from the fact that
you are thinking primarily about endofunctors? In that case every
object and morphism in site lives in the same category, so it is
natural to think that the natural transformations do also. However, I
don't think this is correct. I think it is better to think of
functors as occurring as bridges _between_ categories and natural
transformations as existing _between_ functors. More than just a
collection of morphisms, a natural transformation actually associates
objects and morphisms in the source category with morphisms and
diagrams respectively in the target category. Or, if you prefer the
collection of morphisms in the target category is 'indexed' by the
objects in the source category in such a way that morphisms between
the indexing objects set up a natural relationship between the
morphisms they index - that natural relationship is given by a
commutative diagram.
> I hope these questions make sense. I really appreciate anyone who
> takes to time to read this!
>
> Matt
> _______________________________________________
> Beginners mailing list
> Beginners at haskell.org
> http://www.haskell.org/mailman/listinfo/beginners
More information about the Beginners
mailing list