Direct-style CoT

[KingoftheHomeless]

Found this construction, and I thought I should make an issue here for reference (and possible future inclusion).

Through some isomorphism arithmetic, it's possible to find a direct-style Co:

  forall r. w (a -> r) -> r
~ forall r x. (x -> a -> r) -> w x -> r
~ forall r x. ((x, a) -> r) -> w x -> r
~ forall x. w x -> (x, a)

which is easily generalizable to a monad transformer:

newtype CovT w m a = CovT { runCovT :: forall x. w x -> m (x, a) }

instance Functor m => Functor (CovT w m) where
  fmap f cov = CovT $ \w -> (fmap . fmap) f (runCovT cov w)

instance (Comonad w, Monad m) => Applicative (CovT w m) where
  pure a = CovT $ \w -> pure (extract w, a)
  (<*>) = ap

instance (Comonad w, Monad m) => Monad (CovT w m) where
  m >>= f = CovT $ \w -> do
    (w', a) <- runCovT m (duplicate w)
    runCovT (f a) w'

The obvious difference here is that CovT w m is covariant in m. Also, unlike CoT, CovT (Store s) m is directly isomorphic to StateT s m (rather than the CPS version of StateT). In the same way, CovT ((,) r) m ~ ReaderT r m, CovT ((->) s) m ~ WriterT s m, etc.