← | →

The ReverseT monad transformer

Posted on Friday, 19 November 2010 at 19:59.

{-# LANGUAGE DoRec #-}

import Control.Monad.Fix
import Control.Monad.State
import Control.Monad.Trans

In a two-year-old post Luke Palmer shows an implementation of the Fibonacci sequence using the reverse state monad: a state monad where the results flow forward but the state flows backward.

Similar results can be achieved using the ReverseT monad transformer which reverses the effects of any monad for which the monadic fixpoint mfix :: MonadFix m => (a -> m a) -> m a is defined:

newtype ReverseT m a = ReverseT { runReverseT :: m a }

instance MonadFix m => Monad (ReverseT m) where
  return            = ReverseT . return
  ReverseT m >>= f  =
    ReverseT $ do
      rec
        b <- runReverseT (f a)
 a <- m
 return b

instance MonadTrans ReverseT where
 lift = ReverseT

With this transformer we can write Luke's computeFibs as follows:

cumulativeSums = scanl (+) 0

computeFibs =
  flip evalState [] . runReverseT $ do
    fibs <- lift get
    lift $ modify cumulativeSums
    lift $ put (1:fibs)
    return fibs

Are there any other monads m for which ReverseT m is interesting?

Comments

By Sebastian Fischer on Saturday, 20 November 2010 at 05:21:

Interesting!

When I lift `MonadPlus` like this:

mzero = lift mzero
mplus a b = lift (runReverseT a `mplus` runReverseT b)

It does not play nicely with guard:

ghci> runReverseT (return True >>= guard) :: [()]
loops

Can this be fixed?

By Sjoerd Visscher on Saturday, 20 November 2010 at 11:47:

Sebastian: no, you’re using a value before it is returned. Your code is equivalent to:

do
  rec
    b <- guard a
    a <- return True
  return b

Leave a comment!

Martijn loves to receive comments! Add yours by filling out the fields below.