The update monad which generalizes the reader, writer and state monad from http://homepages.inf.ed.ac.uk/s1225336/talks/types13.pdf

updatemonad.hs

{-# LANGUAGE TypeSynonymInstances, FlexibleInstances, MultiParamTypeClasses #-}

import Data.Monoid
import Data.Monoid.Action
import Data.Monoid.MList (SM(..))
import Control.Monad.Trans.Class


newtype UpdateT p s m a = UpdateT { runUpdateT :: s -> m (p, a) }

instance (Action p s, Monoid p, Monad m) => Monad (UpdateT p s m) where
  return x = UpdateT $ \_ -> return (mempty, x)
  m >>= f = UpdateT $ \s -> do
    (p, x) <- runUpdateT m s
    (p', y) <- runUpdateT (f x) (act p s)
    return (p `mappend` p', y)

instance Monoid p => MonadTrans (UpdateT p s) where
  lift m = UpdateT $ \_ -> do
    a <- m
    return (mempty, a)

get :: (Monoid p, Monad m) => UpdateT p s m s
get = UpdateT $ \s -> return (mempty, s)

put :: Monad m => p -> UpdateT p s m ()
put p = UpdateT $ \_ -> return (p, ())


type ReaderT r = UpdateT () r
runReaderT :: Monad m => ReaderT r m a -> r -> m a
runReaderT m r = do
  ((), a) <- runUpdateT m r
  return a

type WriterT w = UpdateT (SM w) ()
runWriter :: Monad m => WriterT w m a -> m (w, a)
runWriter m = do
  (SM w, a) <- runUpdateT m ()
  return (w, a)

type StateT s = UpdateT (Last s) s
instance Action (Last s) s where
  act (Last Nothing) s = s
  act (Last (Just s)) _ = s
runState :: Monad m => StateT s m a -> s -> m (s, a)
runState m s = do
  (s', a) <- runUpdateT m s
  return (act s' s, a)

type RWST r w s = UpdateT ((), (w, Last s)) (r, s)
instance (Action p1 s1, Action p2 s2) => Action (p1, p2) (s1, s2) where
  act (p1, p2) (s1, s2) = (act p1 s1, act p2 s2)
runRWST :: Monad m => RWST r w s m a -> r -> s -> m (w, s, a)
runRWST m r s = do
  (((), (w, s')), a) <- runUpdateT m (r, s)
  return (w, s, a)