CODEWITHSUNDEEP
haskellfunctorcategory-theory
Clinton
Clinton

Reputation: 23135

Issues Generalising Functor

Functor in Control.Categorical.Functor has the following definition:

class (Category r, Category t) => Functor f r t | f r -> t, f t -> r where
  fmap :: r a b -> t (f a) (f b)

But lets say I want to have a functor from ordinary functions to Kleisli arrows (this is perhaps a silly example) .

I'd want a type like this:

fmap :: (Monad m) => (a -> b) -> Kleisli m a b

Well I can let r = (->), t = Kleisli m to get:

fmap :: (Monad m) => (a -> b) -> Kleisli m (f a) (f b)

But then, what's f?! I really just want it to disappear. I could use the Identity functor by letting f = Identity but then I get:

fmap :: (Monad m) => (a -> b) -> Kleisli m (Identity a) (Identity b)

which would require some messy unwrapping.

I then thought of defining Functor like this:

class (Category r, Category t) => Functor r t where
  type family F r t x :: *
  fmap :: r a b -> t (F r t a) (F r t b)

This allows me to define a Functor instance for Kleisli as follows (without an ugly Identity wrapper):

instance (Monad m) => Functor (->) (Kleisli m) where
  type F (->) (Kleisli m) a = a
  fmap f = Kleisli (return . f)

And after this, I'm pretty sure I'm at:

fmap :: (Monad m) => (a -> b) -> Kleisli m a b

Which is good.

Now, there's one issue I can identify straight away namely, for a given r and t parameters to Functor, the original class definition allows multiple options for f, whereas with my definition, r and t determine f. This is a serious problem, as if I define say:

fmap :: (a -> b) -> (Maybe a -> Maybe b)

I can't then define:

fmap :: (a -> b) -> ([a] -> [b])

As in both cases, r = (->) and t = (->). So currently my Functor doesn't even replace the original Prelude version.

So there's some questions I now have:

  1. Can I adjust my definition so r and t do not determine f (like the original version)? Or would this require Injective Type Families (I'm happy to compile head to try this if this is the case).
  2. Can I further adjust my definition so that f and r determines t and also f and t determines r?
  3. After doing the above (or not if it's not possible) what are the potential impacts on type inference?
  4. Are there any other bad things about my class definition as compared to the original, other than things like increased typing?
  5. Are there any alternate approaches that still allow me to define the Kleisli functor without wrapping with Identity whilst being "better" that what I've proposed (more useful structure, better type inference etc).

I'm sorry the last few questions are a bit vague, I understand that type inference vs generality is often a tradeoff, but I'm just looking for some thoughts on it in this particular case.

(This question partly follows on from answers to this question)

Upvotes: 2

Views: 85

Answers (1)

leftaroundabout
leftaroundabout

Reputation: 120751

The closest you could get would be

class (Category r, Category t) => Functor
          (f :: *) (r :: *->*->*) (t :: *->*->*) where
  type F f x :: *
  fmap :: Tagged f ( r a b -> t (F f a) (F f b) )

instance Functor [()] (->) (->) where
  type F [()] x = [x]
  fmap = Tagged map

instance (Monad m) => Functor (Kleisli m () ()) (->) (Kleisli m) where
  type F (Kleisli m () ()) x = x
  fmap = Tagged $ \f -> Kleisli $ return . f

Upvotes: 3

Related Questions