ansaurus

Question

Answer 1

+9 A:

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.

camccann 2010-07-17 22:13:25

This is a bit of a tangent, but I wanted to check my understanding: a mapping from Maybe a to [a] can be thought of in a number of ways: (a) A functor, where Maybe and [] form sub-categories of Hask. (b) A natural transformation, where Maybe and [] form endofunctors on Hask. (c) A family of morphisms in the category Hask, from Maybe a to [a] forall a in Obj(Hask).Is that all correct?

pelotom 2010-07-17 22:49:20

Addendum: (a) and (b) are of course contingent on the mapping satisfying the laws of functors and natural transformations, respectively. Is it fair to say that if the functor laws are satisfied for (a), then the same mapping can be viewed as (b), and vice versa?

pelotom 2010-07-17 22:57:10

@Tom: I... think so? It sounds right to me. In fact, I think any function with the type `forall a. Maybe a -> [a]` *must* be a natural transformation. `maybeToList` in Data.Maybe, for instance, is (or sufficiently describes) everything you mentioned, I believe, but my own understanding of Category Theory is fairly limited so don't take that as gospel...

camccann 2010-07-17 23:15:45

Great answer, thanks. Question: what is **Hask^(op)**?

Jonathan Sterling 2010-07-18 00:03:55

@Jonathan: that would be the dual category of Hask, which has the same objects as Hask but all morphisms are reversed. See http://en.wikipedia.org/wiki/Opposite_category

pelotom 2010-07-18 00:25:26

@Jonathan Sterling: What @Tom said. A simple example in Haskell is a functor that maps any type `a` to the type `(a -> t)` for some fixed `t` and any function `a -> b` to a function `(b -> t) -> (a -> t)`. This is the dual of the standard `Functor` mapping `a` to `(t -> a)` for a fixed `t`, better known as the `Reader` monad.

camccann 2010-07-18 00:58:08

Answer 2

+4 A:

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

Gian 2010-07-17 22:30:33

For what it's worth, monads in the standard Category Theory sense are indeed defined as endofunctors, whereas the `Monad` type class is a narrower concept, both in the same ways as I describe for `Functor` and with some additional complications resulting from the very invasive cartesian-closed structure of **Hask**.

camccann 2010-07-17 22:49:38

Answer 3

+2 A:

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.

Alexandre C. 2010-07-19 09:07:42

Thanks a lot. I may check out that book.

Jonathan Sterling 2010-07-19 14:44:34

Be warned that you must read this book with a _purpose_ (either functional programming, or algebraic geometry, or whatever), because it is quite terse regarding examples, and you are somehow required to provide _yours_. That makes it an incredibly flexible book though, used by scientists of very diverse horizons.

Alexandre C. 2010-07-19 15:11:59

ansaurus

tags:

views:

answers:

Are all Haskell functors endofunctors?

related questions