Is it possible to implement this generic flip?

Question

I would like to write an object with the type signature:

genericFlip ::
  ( MonadReader (o (n c)) m
  , MonadReader a n
  , MonadReader b o
  )
    => m (n (o c))

That is essentially a flip for monad readers.

Now it is easy enough to write the version of this that looks like:

genericFlip ::
  ( MonadReader (b -> a -> c) m
  , MonadReader a n
  , MonadReader b o
  )
    => m (n (o c))
  genericFlip = do
    f <- ask
    return $ do
      a <- ask
      return $ do
        b <- ask
        return $ f b a

Or even substitute (->) for Reader, but no matter how I wrack my brain I can't seem to make a definition that works for all readers.

Is it possible to make a total object that has this type signature in Haskell?

Answer 1

No. It's not possible.

There's nothing about the first signature that makes o traversable.

Answer 2

Simply by relying on MonadReader you can't, but with Traversable you can get this:

genericFlip :: (Traversable o, MonadReader (o (n c)) m, Monad n) => m (n (o c))
genericFlip = do
  onc <- ask
  return $ sequence onc

Adding other MonadReader constraints will not do any harm, but I can't see exactly what you are trying to achieve with those monads or their environments.

genericFlip ::
  (Traversable o, MonadReader (o (n c)) m, MonadReader a n, MonadReader b o) => m (n (o c))
genericFlip = asks sequence

An example could possibly help.

Answer 3

To begin with, I suggest not generalising m to MonadReader. In the type of flip...

flip :: (a -> b -> c) -> (b -> a -> c)

... the middle arrow is not like the others: it merely links the input and the output of the flip. Adopting that simplification, we end up with a simpler type for the genericFlip you propose:

genericFlip :: (MonadReader a n, MonadReader b o) => o (n c) -> n (o c)

In any case, genericFlip can't be implemented with this signature. On its own, the MonadReader interface doesn't provide a way to supply an environment to a computation, which would be necessary for swapping the layers. Consider, for instance, the specialised genericFlip from your question:

genericFlip' :: (MonadReader a n, MonadReader b o) => (b -> a -> c) -> n (o c)
genericFlip' f = do
  a <- ask
  return $ do
    b <- ask
    return $ f b a

It fundamentally relies on f being a function, which means we can supply environments to it (and, as you note, were we using Reader instead we could do the same thing through runReader). Ultimately, all MonadReader does here is turning functions into reader computations, as made transparent by this pointfree spelling:

genericFlip' :: (MonadReader a n, MonadReader b o) => (b -> a -> c) -> n (o c)
genericFlip' = fmap reader . reader . flip

One generalisation of flip we do have is distribute:

distribute :: (Distributive g, Functor f) => f (g a) -> g (f a)

distribute @((->) _) is also known as flap or (??), while distribute @((->) _) @((->) _) is flip itself.

Distributive, though, doesn't quite untie us from functions in the way we might hope in the context of this question. Every distributive functor is isomorphic to (->) r for some specific r. The connections become more evident when we look at the Representable class, which is in principle equivalent to Distributive, but uses a more sophisticated encoding that makes the isomorphism explicit. In addition to distribute being a generalisation of flip, we have index as a function application analogue, and tabulate, which looks a lot like reader. The class, in fact, offers a default MonadReader implementation, which can be conveniently derived via the Co newtype.

On a final note, something that, in spite of not exactly fitting our proposed generalised flip signatures, is very much flippable is ReaderT r (ReaderT s m) a, which boils down to r -> s -> m a. That is arguably not all that useful, though, as in practice one typically would, rather than having nested reader layes, combine the environments into a single type and have just one reader layer (see also the RIO monad).