An implementation of the reverse state monad with the extra newtype wrapping and unwrapping needed to actually make it work:

reverse-state.hs

newtype RState s a = RState (s -> (a, s))

-- takes initial state s and outputs both a result and a new state
runRState :: RState s a -> s -> (a, s)
runRState (RState f) start = f start

instance Monad (RState s) where
  return x = RState $ \ s -> (x, s)
  RState step1 >>= step2 = RState $ \ start ->
    let (resultA, final)        = step1 intermediate 
        (resultB, intermediate) = runRState (step2 resultA) start in
    (resultB, final)

get = RState $ \ s -> (s, s)
put s' = RState $ \ _ -> ((), s')

nats = do ns <- get
          put (0 : map (+ 1) ns)
          return ns

Idiomatically, I would actually implement runRState using record syntax:

newtype RState s a = RState { runRState :: a -> (a, s) }

but it's confusing if you're never seen the pattern before.