8

The function from a -> m b to m (a -> b) rarely appears in programming, but can be made in the Reader monad. The following code is a tentative implementation. Does such a library exist?

class Monad m => MonadShift m where
  shift :: (a -> m b) -> m (a -> b)

instance MonadShift Identity where
  shift f = Identity (\x -> runIdentity (f x))

instance MonadShift m => MonadShift (ReaderT r m) where
  shift f = ReaderT (\r -> shift (\x -> runReaderT (f x) r))
duplode
  • 33,731
  • 7
  • 79
  • 150
Hexirp
  • 410
  • 2
  • 11
  • 1
    You might also want to read [Turning `A -> M B` into `M (A -> B)`](https://stackoverflow.com/questions/27267848/turning-a-mb-into-ma-b) which explains that there is no way to implement that for general monads, so we really need to use a typeclass for that. – chi Apr 04 '23 at 11:50

2 Answers2

14

It's a specialization of distribute :: Functor f => f (g a) -> g (f a) of the Distributive class where f is the Functor (->) b. Then you get the type signature:

distribute :: (b -> g a) -> g (b -> a)

Note that (1) this doesn't require g to be a Monad, but just a Functor, and (2) the Identity and ReaderT instances are basically the only instances that you can define:

Categorically every Distributive functor is actually a right adjoint, and so it must be Representable endofunctor and preserve all limits. This is a fancy way of saying it is isomorphic to (->) x for some x.

Noughtmare
  • 9,410
  • 1
  • 12
  • 38
  • On note (1), it's worth mentioning that all distributive functors are monads, even though the `Data.Distributive` formulation doesn't express that for technical reasons. That being so, asking `Distributive` is stronger than asking just for `Monad`. – duplode Apr 07 '23 at 23:56
5

This question provides a nice opportunity to collect information about this function that is scattered across multiple Q&As around here. Since it doesn't really have a standard name, I will just call it shift like you did.

As Noughtmare points out, one way in which shift arises is as a specialisation of distribute:

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

shift :: Distributive g => (r -> g a) -> g (r -> a)
shift = distribute @_ @((->) _)

If we instead specialise g, the other functor in the type of distribute, to a function functor, we get a combinator variously known as flap or (??):

flap :: Functor f => f (s -> a) -> (s -> f a)
flap = distribute @((->) _)
-- flap m s = (\f -> f s) <$> m

(If we do both specialisations at once, we end up with flip from the Prelude.)

Since distribute . distribute = id, shift and flap are full inverses:

flap . shift = id
shift . flap = id

Given a distributive functor g, shift and flap therefore give us an isomorphism between Kleisli arrows a -> g b and static arrows g (a -> b). That reflects how the monad and applicative instances of a distributive functor are ultimately equivalent. Such a fact is more readily verified for the function functor, and extends to the other distributives through the Representable isomorphism alluded to by Noughtmare's answer. (By the way, all distributive functors are indeed monads, even though that is not obvious from looking at Data.Distributive given how the API of said module is currently laid out.)

Lastly, while shift is a specialisation of distribute, it is possible to turn things around and express distribute in terms of shift:

distribute m = (\p -> p <$> m) <$> shift id

We can think of shift id :: Distributive g => g (g a -> a) as holding at each position of the distributive functor shape a g a -> a extractor for that position, which is bound to p in the definition above. That being so, mapping over shift id makes it possible to pick values from matching positions within m :: f (g a).

duplode
  • 33,731
  • 7
  • 79
  • 150