Are all Haskell functors endofunctors?

Question

I'm a bit confused, and need someone to set me straight. Lets outline my current understanding:

Where E is an endofunctor, and A is some category:

E : A -> A.

Since all types and morphisms in Haskell are in the Hask category, is not any functor in Haskell also an endofunctor? F : Hask -> Hask.

I have a good feeling that I'm wrong, and oversimplifying this somehow, and I'd like someone to tell me what an idiot I am. Thanks.

Answer 1

You may want to clarify whether you're asking about "functors in Haskell", or Functors. It's not always clear what category is being assumed when Category Theory terms are used in Haskell.

But yes, the default assumption is Hask, which is taken to be the category of Haskell types with functions as morphisms. In that case, an endofunctor F on Hask would map any type A to a type F(A) and any function f between two types A and B to a function F(f) between some types F(A) and F(B).

If we then limit ourselves to only those endofunctors which map any type a to a type (f a) where f is a type constructor with kind * -> *, then we can describe the associated map for functions as a higher-order function with type (a -> b) -> (f a -> f b), which is of course the type class called Functor.

However, one can easily imagine well-behaved endofunctors on Hask which can't be written (directly) as an instance of Functor, such as a functor mapping a type a to Either a t. And while there's obviously not much sense in a functor from Hask to some other category entirely, it's reasonable to consider a (contravariant) functor from Hask to Hask^op.

Beyond that, instances of Functor necessarily map from the entire category Hask onto some subset of it that, thus, also forms a category. But it's also reasonable to talk about functors between subsets of Hask. For instance, consider a functor that sends types Maybe a to [a].

You may wish to peruse the category-extras package, which provides some Category Theory-inspired structures embedded within Hask instead of assuming the entirety of it.

Answer 2

Even if ultimately, you manipulate Hask, there are a lot of other categories that can be built on Hask, which can be meaningful for the problem at hand:

• Hask^op, which is Hask with all arrows reversed
• Hask * Hask, functors on it are bifunctors
• Comma categories, ie. objects are morphisms to a fixed object a, morphisms are commutative triangles
• Functor categories, morphisms are natural transformations
• Algebra categories
• Monoidal categories
• Kleisli categories
• ...

grab a copy of Mac Lane's Categories for the Working Mathematician to have definitions, and try to find by yourself the problem they solve in Haskell. Especially choke on adjoint functors (which are initial/terminal objects in the right category) and their relationship with monads.

You'll see that even if there is one big category (Hask, or perhaps "lifted objects from Hask with the right arrows/products/...", which encapsulates the language choices of Haskell such as non-strictness and lazyness), proper derived categories are expressive.

Answer 3

A possibly relevant (or at least interesting) discussion specifically regarding monads is found in the paper "Monads need not be endofunctors":

http://www.cs.nott.ac.uk/~txa/publ/Relative_Monads.pdf