[Haskell-cafe] Relating functors in Category Theory to Functor

[ajb at spamcop.net]

G'day all.

Quoting David Menendez <zednenem at psualum.com>:

> Until recently, I've had difficulty relating the concept of a "functor"
> from Category Theory to the class Functor in Haskell.

[...]

> We can interpret Haskell as a category with types as objects and
> functions as morphisms. For example, isDigit :: Char -> Bool.
>
> So, for some Functor f, the type constructor f corresponds to F[ob], and
> fmap to F[mor]. For any function g :: a -> b, fmap g :: f a -> f b, and
> fmap (g . h) = fmap g . fmap h.

Correct.

Technically, Functor should probably be called Endofunctor, because
it's actually a functor from the category Haskell to the category
Haskell.  That would probably just confuse things more, though. :-)

> For two functors F, G: C -> D, there is a natural transformation tau
> from F to G, if for every object a in C, there is morphism tau[a]: F(a)
> -> G(a) in D.
>
> In Haskell, natural transformations are polymorphic functions, tau :: f
> a -> g a. For example, maybeToList :: Maybe a -> [a].

Not quite.  A natural transformation is a mapping between _functors_.
In this case, maybeToList is a natural transformation between Maybe
and [].  Expressing this as a typeclass is left as an exercise, but
here's a start:

        class (Functor f, Functor g) => NaturalTransformation ... where
            ...

> A monad is a functor, F: C -> C, plus two natural transformations mu:
> F^2 -> F and eta: I -> F (I being the identity functor for C).
>
> In Haskell, F[ob] becomes the type constructor, F[mor] becomes fmap (or
> liftM), mu becomes join :: f (f a) -> f a, and eta becomes return :: a
> -> f a.

Yup!  Handily, all Haskell Functors are endofunctors, so Haskell monads
don't need the extra constraint that F must be an endofunctor.

Cheers,
Andrew Bromage