# Mindfuck: The Reverse State Monad

Someone in the #haskell IRC channel mentioned the “reverse state monad” explaining that it used the state from the next computation and passed it to the previous one. Well, I just had to try this!

First, a demonstration: we will compute the fibonacci numbers by starting with them and mapping them back to the empty list.

```-- cumulativeSums [1,2,3,4,5] = [0,1,3,6,10,15]
cumulativeSums = scanl (+) 0

computeFibs = evalRState [] \$ do
-- here the state is what we want: the fibonacci numbers
fibs <- get
modify cumulativeSums
-- now the state is the difference sequence of
-- fibs, [1,0,1,1,2,3,5,8,13,...], because the
-- cumulativeSums of that sequence is fibs.  Notice
-- that this sequence is the same as 1:fibs, so
-- just put that to get here.
put (1:fibs)
-- And here the state is empty (or whatever else
-- we want it to be, because we just overwrite it on
-- the previous line -- but we defined it to be
-- empty on the evalRState line)
return fibs
```

And sure enough:

```>>> take 15 computeFibs
[0,1,1,2,3,5,8,13,21,34,55,89,144,233,377]
```

And now the implementation:

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

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
```

The important part is the definition of (>>=). Notice how the data (a,b) flows forward, but the state (s,s’,s”) flows backward.

## 18 thoughts on “Mindfuck: The Reverse State Monad”

1. Gleb says:

Mind-bending stuff. I wonder if it can be of any use in “real world” ™.

By the way, I believe “import Control.Arrow (first)” is not used here.

2. Anon says:

Could be fun for Undo.

3. Is there another example that isn’t simpler than *not* using the monad?
``` > let fibs = cumulativeSums (1:fibs) in take 15 fibs [0,1,1,2,3,5,8,13,21,34,55,89,144,233,377] ```

4. Gosh, what is it with you people and your “real world”? Isn’t imperative-looking code that has hauntingly freaky semantics when you interpret it imperatively enough? Why does everything have to have a use?

5. Gleb says:

Luke, the “(tm)” after “real world” was there as a hint that I was rather sceptical myself about existence of the single real world for everybody. I was just curious, no offence intended.

6. Ryan Ingram says:

The reverse state monad is actually quite useful for implementing an efficient writer monad that generates data structures that get accessed lazily; in this case the access to the “tail” of the data structure is naturally deferred until later, so even though the internals of the monad make it look like the state is moving backwards, it is actually moving forward. Here’s a simple example:

yield s = modify (s:)

lazy = do
yield “start”
let x = last [1..1000000000] :: Int
yield (show x)
yield “done”

test = mapM_ putStrLn \$ snd \$ runRState lazy []

Running “test” will immediately print “start”, then wait a while, then print “1000000000” and “done” in short succession; the lazy list consumption runs -forward- through the computation exactly because the state flows backwards.

Contrast this with using the usual state monad, leaving the definition of “yield” alone, and then reversing the list at the end; the result is the same, but “reverse” cannot do anything until the entire list has been constructed.

7. Ryan Ingram says:

To continue, using “yield” in this way will make people familiar with stream generators in python & ruby get a warm fuzzy feeling.

fibGen x y = do
yield y
fibGen y (x+y)

fibs = snd \$ runRState (fibGen 0 1)
\$ error “fibs should be infinite”

8. Gleb: no worries, my comment was meant tongue-in-cheek.

Ryan: is this superior to Writer [] or Writer (Dual []) (I never remember which one is more efficient) with yield = (:[]) in any way?

9. Leon says:

Cute. At first I wasn’t sure this was a monad, but the laws check out. Useful? I dunno.

Your example is a circular program. However, I’ve run into trouble trying to employ this on my favorite corecursive examples.

I’m going to have to spend some time playing around with this one. Thanks for writing it up!

10. Ryan Ingram says:

> is this superior to Writer []
> or Writer (Dual [])
> with yield = (:[]) in any way?

Yes, actually. It’s basically the same as Writer (DList a), though.

Both versions of Writer have n^2 behavior on badly-behaved input data. Here’s a code sample that demonstrates the problem for both:

foo 0 = tell [0]
foo (n+1) = tell [-n] >> foo n >> tell [n]

It also was easier for me to grok than Writer; the state monad just made more sense to me (coming from a C/C++ background). Writer didn’t make any sense for a long time, mostly due to me missing the Monoid constraint on w.

The reverse state monad took a bit longer for me to grok, but I was able to imagine the “rest” of the state racing forward along with the computation as elements were consumed. Your “fibs” example seems pretty magical, though :)

11. Andrew says:

I just googled “state monad simple example” and this link cropped up. Needless to say that’s not a simple example of the use of a state monad, its actually quite the opposite :P Cool stuff though from what I managed to comprehend. Makes me more earnest to want to understand these monads. Unfortunately I can’t really. I’ve read many tutorials, each with different point of view but they stay at the very edge of my knowledge.

Sorry if I bothered ya with my voyage through the monadic word.

12. Anonymous says:

Hah! I am SO going to use this in my compiler assignment! :D

13. Anonymous says:

Part of my parser now:

after <- getLast
t1 <- parseExpr e
parseStmt s
pushLast_

14. benmachine says:

eep, something awful happened to my comment. let’s try that again

stateToRState :: State s a → RState s a
stateToRState st = RState \$ \s → runState st s

rstateToState :: RState s a → State s a
rstateToState st = do
(a,s) ← gets (runRState st)
put s
return a

— doing this with the RState get/put gives an infinite loop for obvious reasons
rputSnd :: a → RState (c,a) ()
rputSnd x = stateToRState \$ do
(c,_) ← get
put (c,x)

here’s hoping the blog handles unicode arrows better than it handles left angle brackets!

15. Luke says:

@benmachine, that makes sense. Hmm, are RState and State categorically related?

16. Anonymous says:

Is the backward state monad’s applicative the same as the state monad’s backward applicative?