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)

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

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

About these ads

18 thoughts on “Mindfuck: The Reverse State Monad

  1. 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. 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]

  3. 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?

  4. 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.

  5. 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.

  6. 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”

  7. 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?

  8. 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!

  9. > 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 :)

  10. 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.

  11. Part of my parser now:

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

  12. 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
    — so we temporarily thread the state forwards instead :)
    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!

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s