"Transposition" of functors?

Question

Recently I had to write the following function:

mToL :: Maybe [a] -> [Maybe a]
mToL Nothing = []
mToL (Just xs) = map Just xs

This begged the question whether it is possible to generalize the above to:

transposeF :: (Functor f, Functor g) => f (g a) -> g (f a)

I guess it only works if there is a way to "collapse" f (g a) into f a, or is there any other way?

Answer 1

Actually, there is a type class that would support this. It's not included in the standard type class but "representable functors" have this capability.

A representative functor is a functor F with two things

1. a type A
2. An isomorphism between F and (->) A

We could represent this as

 type family ReprObj (f :: * -> *):: *

 class Functor f => Repr f where
   toHom   :: f a -> (ReprObj f -> a)
   fromHom :: (ReprObj f -> a) -> f a

where toHom . fromHom = fromHom . toHom = id. An example of a representable functor,

 newtype Pair a = Pair (a, a) deriving Functor
 type instance ReprObj Pair = Bool

 instance Repr Pair where
   toHom (Pair (a, b)) True  = a
   toHom (Pair (a, b)) False = b
   fromHom f = Pair (f True, f False)

Now using this we can derive

swap :: (Functor f, Functor g, Repr f, Repr g) => f (g a) -> g (f a)
swap g = fromHom $ \obj -> fmap ($ obj) hom
   where hom = fmap toHom g

In fact, we can also get a free applicative and monad instance out of representable functors. I detailed how you could do this in a blog post.

Answer 2

The Traversable typeclass provides the sequence and sequenceA operations, which provide the most general solutions to your problem, but they require different constraints:

sequence :: (Traversable t, Monad m) => t (m a) -> m (t a)

sequenceA :: (Traversable t, Applicative f) => t (f a) -> f (t a)

Answer 3

This is not possible in general, no. Set f to Const b and g to Identity.

newtype Const b a = Const { getConst :: b }
newtype Identity a = Identity { runIdentity :: a }

These are both obviously functors with their normal instances. transposeF can't work because Const b doesn't supply any as with which to wrap with Identity. So you can't write the transposition function.

On the other hand, this is nice for a whole lot of Functor pairings. The categorical notion is that of the adjoint functor and once you see them, you'll start seeing them everywhere. They're a very powerful notion in their own right.

Answer 4

It's not possible to do so using functors simply because there's no generic way to unwrap a functor value:

Prelude> :info Functor
class Functor f where
  fmap :: (a -> b) -> f a -> f b
  (GHC.Base.<$) :: a -> f b -> f a
    -- Defined in `GHC.Base'
instance Functor Maybe -- Defined in `Data.Maybe'
instance Functor (Either a) -- Defined in `Data.Either'
instance Functor [] -- Defined in `GHC.Base'
instance Functor IO -- Defined in `GHC.Base'
instance Functor ((->) r) -- Defined in `GHC.Base'
instance Functor ((,) a) -- Defined in `GHC.Base'

Instead you could create your own typeclass to provide a generic transpose function as follows:

import Control.Applicative

class Applicative f => Transposable t where
    unwrap :: t a -> a
    transpose :: s (t a) -> t (s a)
    transpose = fmap pure . unwrap

The reason we make Applicative a superclass of Transposable is so that we can use its pure method. All instances of Applicative are also instances of Functor.