`instance MFunctor t => MFunctor (Psi t) ...`

[michaelt]

It seems I very frequently run into trouble with MFunctor instances that carry an MFunctor constraint forward. This is probably not a legitimate type, but consider:

newtype Stream t m r = Stream {runStream :: m (Either r (t m (Stream t m r)))}

Writing a functor instance is simple

instance (Monad m, Functor (t m)) => Functor (Stream t m) where
   fmap f = Stream . liftM (either (Left . f) (Right . fmap (fmap f))) . runStream

but if I set out to write

instance (MFunctor t) => MFunctor (Stream t) where
  hoist phi = loop where 
    loop (Stream me) = Stream $ phi $ do
      e <- me
      case e of
        Left r   -> return $ Left r
        Right tr -> return $ Right $ hoist phi (fmap loop tr)

of course I get the complaint that

 Could not deduce (Functor (t m)) arising from a use of ‘loop’
 from the context (MFunctor t)

But the constraint can't be added, since m is not in scope. One can do an end run around this:

newtype Stream t m r = Stream {runStream :: m (Either r (t m (Stream t m r)))}

class RFunctor t where
  rmap :: forall m a b . Monad m => (a -> b) -> t m a -> t m b

instance RFunctor t => RFunctor (Stream t) where 
  rmap f = Stream . liftM (either (Left . f) (Right . rmap (rmap f))) . runStream

instance (Monad m, RFunctor t) => Functor (Stream t m) where fmap = rmap 

instance (MFunctor t, RFunctor t) => MFunctor (Stream t) where
  hoist phi = loop where 
    loop (Stream me) = Stream $ phi $ do
      e <- me
      case e of
        Left r   -> return $ Left r
        Right tr -> return $ Right $ hoist phi (rmap loop tr)

Am I missing some simpler device? I have bumped to this more than once; maybe here I have a bad instance, but it will it think be a distraction to meditate on the particular case. It is fairly typical that you need a stronger fmap where you write instance (MFunctor t) => MFunctor (... t ...) since you can't presuppose (forall m. Monad m => Functor (t m))

It occurred to me that something like RFunctor (pardon the dumb name) could be a constraint on MFunctor or the slightly strengthened fmap could be included in its methods. But I don't know.

[michaelt]

A clearer statement of the difficulty: where we add a new MFunctor instance based on an old one, the actual implementation that uses the constrained t :: (* -> *) -> * -> * will have to saturate t with some f or m in order to use hoist on t m _. But where I use hoist in writing the instance I am almost certain to want to use fmap. But (t f) or (t m) can't be mentioned in the constraint, since f or m can't ... since it's an MFunctor instance we are defining.

[Gabriella439]

I agree that something like RFunctor is the correct solution. I'd be happy to add that class to mmorph in some way, although maybe under another name. However, I don't think it needs to be a constraint on the MFunctor class. Just make it a constraint on your instance:

instance (RFunctor t, MFunctor t) => MFunctor (Stream t)

[michaelt]

Yes, the name was just to get it written down. I was only hooking it up with MFunctor because that was the only place I needed it. Once I defined it it was nicer than the Monad m, Functor (t m) => in some other contexts.

Maybe the method could called

fmaps :: Monad m => (a -> b) -> t m a -> t m b

to express that fmaps works the same for any monad or something like that. Then the class could be called, say Functors with the mnemonic intimation that all the t ms are functors, and that this is being expressed in one class. For the transformers types, the trivial instance where fmaps = fmap will always work; this is also the governing law of course.

I just tried these names here https://github.com/michaelt/trans/blob/master/Trans.hs I can't tell if the proximity to Functor is just adding a layer of confusion.

[Gabriella439]

The part I get stuck on here is what to call the class for this. I guess I could follow the Edward convention of Functor2 for naming higher-kinded equivalents of the same class and then use fmap2 as the class method.