Generalizing Functor

(From a couple of conversations in #haskell...) The other day, Peaker was trying to characterize a relationship between Arrow and Functor. I'm not sure I understood his intuition, but there's one relationship that seemed obvious to me...

The Category class represents categories whose objects are Haskell types. Hask is one such category, but obviously there are many others.

class Category c where
  id :: c a a
  (.) :: c b d -> c a b -> c a d

An instance of Category represents a category in terms of its hom-objects in Hask. In other words, the type c a b (as an object in Hask) represents the set of morphisms a -> b in the category C defined by the instance.

(Aside: Values of type c a b represent individual C-morphisms a -> b, as the definition of id makes clear, but when working with categories, we're forced into a point-free style, because we have no notion of lambda abstraction for an arbitrary category.)

Anyway, all this is to say that we're representing a category C by its hom-functor c: C x C -> Hask (or really C -> C -> Hask, but let's ignore that detail...), so we'd expect the type constructor c to be a bi-functor. In particular, we'd expect the type constructor c a to be a functor. But we run into trouble if we try to say so:

instance Category c => Functor (c a) where
  f `fmap` x = ?

We find that we need a way of lifting an arbitrary function a -> b to c a b, which certainly doesn't make sense, and would be a significant restriction on the categories we can represent. (Is this related to people's distaste for arr in Arrows? I think so...) The problem is that Functor only represents functors Hask -> Hask, but c a is a functor C -> Hask. It doesn't matter for the object mapping of the functor, but for fmap, which provides the arrow mapping, it does.

So this leads me to want a "generalized" functor, although really it's just a regular functor that's not restricted to be an endofunctor on Hask. We can write it with type families:

class Gunctor f where
    type Cat1 f :: * -> * -> *
    type Cat2 f :: * -> * -> *
    gmap :: Cat1 f a b -> Cat2 f (f a) (f b)

And now we can express the relationship between Category and Gunctor quite elegantly:

instance Category cat => Gunctor (cat a) where
    type Cat1 (cat a) = cat
    type Cat2 (cat a) = (->)
    gmap = (.)

This simply states quite literally what we already knew: that Category represents a category in terms of its hom-objects in Hask.

Of course, all instances of Functor are also "generalized" functors:

newtype WrappedFunctor f a = WrapFunctor { unwrapFunctor :: f a }

instance Functor f => Gunctor (WrappedFunctor f) where
    type Cat1 (WrappedFunctor f) = (->)
    type Cat2 (WrappedFunctor f) = (->)
    gmap f = WrapFunctor . fmap f . unwrapFunctor

Meanwhile, Cale was musing about another generalization of Functor, and defining (.) for arbitrary functors. I can only understand what he means if we first move from Functor to Gunctor, but I wonder if he actually meant something else...

Anyway, is this useful? I don't know, possibly not. This level of abstraction starts to give GHC a lot of trouble, even with 6.10.1, and it gives my brain some trouble as well. But I tend to feel that way about arrows as a whole, so if arrows are useful, perhaps this more general functor is too.

Tags: