Monad Transformer stacks with MaybeT and RandT

I'm trying to learn how Monad Transformers 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 used a Map for efficient lookups for known key/value pairs (I suppose I could refactor to use an array). So 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

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

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?