Monad Transformer stacks with MaybeT and RandT

Question

I'm trying to learn how Monad Transformers work by re-factoring something I wrote when I first learned Haskell. It has quite a few components that could be replaced with a (rather large) stack of Monad Transformers.

I started by writing a type alias for my stack:

type SolverT a = MaybeT
                    (WriterT Leaderboard
                        (ReaderT Problem
                            (StateT SolutionState
                                (Rand StdGen)))) a

A quick rundown:

• Rand threads through a StdGen used in various random operations
• StateT carries the state of the solution as it gets progressively evaluated
• ReaderT has a fixed state Problem space being solved
• WriterT has a leaderboard constantly updated by the solution with the best version(s) so far
• MaybeT is needed because both the problem and solution state use lookup from Data.Map, and any error in how they are configured would lead to a Nothing

In the original version a Nothing "never" happened because I only used a Map for efficient lookups for known key/value pairs (I suppose I could refactor to use an array). In the original I got around the Maybe problem by making a liberal use of fromJust.

From what I understand having MaybeT at the top means that in the event of a Nothing in any SolverT a I don't lose any of the information in my other transformers, as they are unwrapped from outside-in.

Side question

[EDIT: This was a problem because I didn't use a sandbox, so I had old/conflicting versions of libraries causing an issue]

When I first wrote the stack I had RandT at the top. I decided to avoid using lift everywhere or writing my own instance declarations for all the other transformers for RandT. So I moved it to the bottom.

I did try writing an instance declaration for MonadReader and this was about as much as I could get to compile:

instance (MonadReader r m,RandomGen g) => MonadReader r (RandT g m) where
    ask = undefined
    local = undefined
    reader = undefined

I just couldn't get any combination of lift, liftRand and liftRandT to work in the definition. It's not particularly important but I am curious about what a valid definition might be?

Problem 1

[EDIT: This was a problem because I didn't use a sandbox, so I had old/conflicting versions of libraries causing an issue]

Even though MonadRandom has instances of everything (except MaybeT) I still had to write my own instance declarations for each Transformer:

instance (MonadRandom m) => MonadRandom (MaybeT m) where
    getRandom = lift getRandom
    getRandomR = lift . getRandomR
    getRandoms = lift getRandoms
    getRandomRs = lift . getRandomRs

I did this for WriterT, ReaderT and StateT by copying the instances from the MonadRandom source code. Note: for StateT and WriterT they do use qualified imports but not for Reader. If I didn't write my own declarations I got errors like this:

No instance for (MonadRandom (ReaderT Problem (StateT SolutionState (Rand StdGen))))
  arising from a use of `getRandomR'

I'm not quite sure why this is happening.

Problem 2

With the above in hand, I re-wrote one of my functions:

randomCity :: SolverT City
randomCity = do
    cits <- asks getCities
    x <- getRandomR (0,M.size cits -1)
    --rc <- M.lookup x cits
    return undefined --rc

The above compiles and I think is how transformers are suppose to be used. In-spite of the tedium of having to write repetitive transformer instances, this is pretty handy. You'll notice that in the above I've commented out two parts. If I remove the comments I get:

Couldn't match type `Maybe'
              with `MaybeT
                      (WriterT
                         Leaderboard
                         (ReaderT Problem (StateT SolutionState (Rand StdGen))))'
Expected type: MaybeT
                 (WriterT
                    Leaderboard (ReaderT Problem (StateT SolutionState (Rand StdGen))))
                 City
  Actual type: Maybe City

At first I thought the problem was about the types of Monads that they are. All of the other Monads in the stack have a constructor for (\s -> (a,s)) while Maybe has Just a | Nothing. But that shouldn't make a difference, the type for ask should return Reader r a, while lookup k m should give a type Maybe a.

I thought I would check my assumption, so I went into GHCI and checked these types:

> :t ask
ask :: MonadReader r m => m r
> :t (Just 5)
(Just 5) :: Num a => Maybe a
> :t MaybeT 5
MaybeT 5 :: Num (m (Maybe a)) => MaybeT m a

I can see that all of my other transformers define a type class that can be lifted through a transformer. MaybeT doesn't seem to have a MonadMaybe typeclass.

I know that with lift I can lift something from my transformer stack into MaybeT, so that I can end up with MaybeT m a. But if I end up with Maybe a I assumed that I could bind it in a do block with <-.

Problem 3

I actually have one more thing to add to my stack and I'm not sure where it should go. The Solver operates on a fixed number of cycles. I need to keep track of the current cycle vs the max cycle. I could add the cycle count to the solution state, but I'm wondering if there is an additional transformer I could add.

Further to that, how many transformers is too many? I know this is incredibly subjective but surely there is a performance cost on these transformers? I imagine some amount of fusion can optimise this at compile time so maybe the performance cost is minimal?

Answer 1

Problem 1

Can't reproduce. There are already these instances for RandT.

Problem 2

lookup returns Maybe, but you have a stack based on MaybeT. The reason why there is no MonadMaybe is that the corresponding type class is MonadPlus (or more general Alternative) - pure/return correspond to Just and empty/mzero correspond to Nothing. I'd suggest to create a helper

lookupA :: (Alternative f, Ord k) => k -> M.Map k v -> f v
lookupA k = maybe empty pure . M.lookup k

and then you can call lookupA wherever you need in your monad stack

As mentioned in the comments, I'd strongly suggest to use RWST, as it's exactly what fits your case, and it's much easier to work with than the stack of StateT/ReaderT/WriterT.

Also think about the difference between

type Solver a = RWST Problem Leaderboard SolutionState (MaybeT (Rand StdGen)) a

and

type Solver a = MaybeT (RWST Problem Leaderboard SolutionState (Rand StdGen)) a

The difference is what happens in the case of a failure. The former stack doesn't return anything, while the latter allows you to retrieve the state and the Leaderboard computed so far.

Problem 3

The easiest way is to add it into the state part. I'd just include it into SolutionState.

Sample code

import Control.Applicative
import Control.Monad.Random
import Control.Monad.Random.Class
import Control.Monad.Trans
import Control.Monad.Trans.Maybe
import Control.Monad.RWS
import qualified Data.Map as M
import Data.Monoid
import System.Random

-- Dummy data types to satisfy the compiler
data Problem = Problem
data Leaderboard = Leaderboard
data SolutionState = SolutionState
data City = City

instance Monoid Leaderboard where
  mempty = Leaderboard
  mappend _ _ = Leaderboard

-- dummy function
getCities :: Problem -> M.Map Int City
getCities _ = M.singleton 0 City

-- the actual sample code

type Solver a = RWST Problem Leaderboard SolutionState (MaybeT (Rand StdGen)) a

lookupA :: (Alternative f, Ord k) => k -> M.Map k v -> f v
lookupA k = maybe empty pure . M.lookup k

randomCity :: Solver City
randomCity = do
    cits <- asks getCities
    x <- getRandomR (0, M.size cits - 1)
    lookupA x cits