[Haskell-beginners] Category Theory

[Paul Higham]

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