Real life and useful examples of Reverse State monad

Question

Reverse State monad is really nice and mind blowing example of Haskell language's expressiveness and lazy evaluation. But it's not that easy to understand this monad. Moreover, it's really hard to find some convincing real life example of what you can do with Reverse State monad easier than with any other tool in the language.

Reverse State monad is defined in the next way:

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

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

It already has some examples and usages but I don't find them quite practical.

1. Quora answer: well-explained and even has real life example of usage but without code and it's not clear whether it's a really good idea to use RState.
2. Mindfuck: introducing this nice concept but example is not useful. Nobody will write Fibonacci numbers this way.
3. Kwang's Haskell Blog: shows how Writer can be emulated with RState but come on. Not really a real life example :)

I'm also aware of tardis package but no tutorial of this library, documentation examples are really abstract, not so many people really understand it. The closest to what I want is this tutorial but it has example of tardis, not just RState. As well as this book reference.

Thus I'm not looking for tardis real life patterns, I'm interested only in RState illustration if possible. Though I understand that there might be no samples of pure RState usages. In that case minimal example with RStateT transformer or tardis is good enough.

Did someone use this monad in real life or have really nice & useful illustration with code?

Answer 1

I have known about these monads for well over a decade now, and have only just recently seen a realistic application of them. It's in a bit of an unusual setting. A coworker and I are using functional reactive programming via the 'reflex' library, and are working on a library to help with building terminal-graphics applications. If you're familiar with 'reflex-dom', it's similar in nature, except that our basic monad, rather than putting subsequent widgets one after the other in the DOM, instead just stacks terminal character-cell-based "images" on top of each other, and it's up to the user to carve up the screen sensibly. We wanted to provide something a little nicer than this, which would keep track of remaining screen real-estate to some extent, and let the user place some "tiles" in rows and columns, such that a do-block basically corresponds to either a column or row of tiles on the screen.

In addition to handling the problem of layout, we also want the tiles to be able to manage keyboard focus, allowing the user to press tab to cycle through them, or shift-tab to go in reverse. It was here that the forwards-and-backwards-in-time state monad transformer became quite handy: we can have the current state in either direction be an Event (of an empty tuple). Each tile can send an event to the previous and next widgets (and receive an event from them), notifying widgets when they are receiving keyboard focus and so should stop blocking key presses from reaching their child widgets. So schematically, the tile widget looks something like:

do rec focusP <- recvFromPast
       sendToPast shiftTabPress
       tabPress <- gate focused $ ... filter input Event for Tab keypresses ...
       shiftTabPress <- gate focused $ ... filter input Event for Shift-Tab ...
       focused <- hold False $ leftmost
         [ True <$ (focusP <> focusF)
         , False <$ (shiftTabPress <> tabPress) ]
       v <- ... run the child widget and do layout stuff ...
       sendToFuture tabPress
       focusF <- recvFromFuture
   return v

Here, sendToFuture is the ordinary state "put", sendToPast is the reverse-time "put", recvFromPast is the ordinary state "get", and recvFromFuture is reverse-time "get". So focusP :: Event t () is an Event that we get from our predecessor (another tile like this one, probably) telling us that we have the focus now, and focusF, is a similar Event we receive from our successor. We keep track of when we have the focus using a 'hold' to construct focused :: Behavior t Bool, which is then used to gate the keyboard events so that we're sure to tell our neighbours they're receiving focus only if we ourselves are focused, and is also used in the bit I elided where we're running the child widget, in order to filter its input events appropriately.

I'm not certain we're actually going to still be doing it this way by the time the library gets released, but it seems to work well thus far, and I was happy to have finally noticed a case in which this construction could be put to practical use.