Sat Apr 7 18:09:01 CEST 2012

Reverse State monad

It uses knot tying to construct a bi-directional data flow. From [1]:

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

  instance Monad (RState s) where
      return x = RState $ (,) x
      RState sf >>= f = RState $ \s ->
          let (a,s'') = sf s'
              (b,s') = runRState (f a) s
          in (b,s'')

  get = RState $ \s -> (s,s)
  modify f = RState $ \s -> ((),f s)
  put = modify . const

Probably best to do this instead of the last 3 hardcoded methods:

  -- Is this allowed to be in here?
  instance MonadState s (RState s) where
    get   = RState $ \s -> (s,s)
    put s = RState $ \_ -> ((),s)

And also:

  instance Functor (RState s) where
    fmap = liftM
  instance Applicative (RState s) where
    pure = return
    (<*>) = ap

I don't find this in the standard libraries.  Is it removed?  Maybe
this is now a combination of ReverseT and State?

I used this monad to implement the bridge between traverse and foldr.
This works as long as the hardcoded "modify" is used.  Making RState
part of MonadState results in an infinite list of the same element.
Maybe this is just bottom and a conseqence of the knot-tying
interfering with the default "modify" from MonadState.

  foldr f s b = s' where
    (_, s') = runRState (traverse f' b) s
    f' b = modify (f b)

[1] http://lukepalmer.wordpress.com/2008/08/10/mindfuck-the-reverse-state-monad/