Natural Transformations and friends

[jnape]

A NaturalTransformation<F,G> for some Functor F and some Functor G witnesses the morphism forall a. F a -> G a. Something like the following signature that witnesses the narrowed result type should be sufficient:

interface NaturalTransformation<F extends Functor<?,F>, G extends Functor<?,G>> {
  <A, FA extends Functor<A, F>, GA extends Functor<A, G>> GA apply(FA fa);
}

There should be an obvious and easy way to construct a NaturalTransformation from some base monad to a transformed monad via a Lift<T>.

Pairing a NaturalTransformation<F,G> with a NaturalTransformation<G,F> yields a NaturalIsomorphism<F,G>.

Probably it makes sense to add a mapXXXT(NaturalTransformation<M, N> nat) method to each of the built-in transformers, although there's little prior art in the way of IterateT (since it's "ListT done right"). Current thoughts are an interface isomorphic to something like:

mapIterateT :: (MonadRec m, MonadRec n)
            => (m (Maybe (a, IterateT n b)) -> n (Maybe (b, IterateT n b))) 
            -> (IterateT m a -> Iterate T n b)
mapIterateT f = suspended . f . fmap (fmap (fmap mapIterateT f)) . runIterateT