How do I add lists or ListT to this monad transformer?

Question

I have a game record that represents the current state of a game.

data Game = Game { score :: Int, turn :: Int }

I want to be able to create a bunch of functions to change the game state, and also use a random number generator as well as keep a log of what happened to get from one state to another. So I created a GameState record that contains the additional information.

type History = [String]
data GameState = GameState Game StdGen History

Now I want to create a data type for the functions that are going to be acting on this GameState. They'll be modeled imperatively as updates to the game as well as rolling dice and logging what's happening. So I created a monad transformer of all the effects I want.

type Effect = WriterT History (RandT StdGen (State Game))

Writing the function to run an Effect on a given GameState is pretty simple.

runEffect :: GameState -> Effect () -> GameState
runEffect (GameState game stdGen history) effect =
  let ((((), newHist), newGen), newGame) =
        runState (runRandT (runWriterT effect) stdGen) game
  in GameState newGame newGen newHist

Perfect. Now I want to model one additional thing. Some Effects can have multiple different resulting GameStates. So my runEffect should actually return a [GameState]. I need to add ListT to this monad transformer, probably. And then all of my Effects will have the option of producing more than one result if need be. But also if they are just a one-to-one mapping then then can act like that too.

I tried to make the following changes:

type Effect2 = ListT (WriterT [String] (RandT StdGen (State Game)))

runEffect2 :: GameState -> Effect2 a -> [GameState]
runEffect2 (GameState game stdGen history) effect =
  let l = runListT effect
      result = map (\e->runState (runRandT (runWriterT e) stdGen) game) l
  in map (\((((), newHist), newGen), newGame)->
           GameState newGame newGen newHist)
         result

What I'm trying to do is add ListT to the transformer, outside of the Writer and Random and State because I want for the different branches of the computation to have different histories and independent states and random generators. But this doesn't work. I get the following type error.

Prelude λ: :reload [1 of 1] Compiling Main             ( redux.hs, interpreted )

redux.hs:31:73: error:
    • Couldn't match expected type ‘[WriterT
                                       w
                                       (RandT StdGen (StateT Game Data.Functor.Identity.Identity))
                                       a1]’
                  with actual type ‘WriterT [String] (RandT StdGen (State Game)) [a]’
    • In the second argument of ‘map’, namely ‘l’
      In the expression:
        map (\ e -> runState (runRandT (runWriterT e) stdGen) game) l
      In an equation for ‘result’:
          result
            = map (\ e -> runState (runRandT (runWriterT e) stdGen) game) l
    • Relevant bindings include
        result :: [(((a1, w), StdGen), Game)] (bound at redux.hs:31:7)
        l :: WriterT [String] (RandT StdGen (State Game)) [a]
          (bound at redux.hs:30:7)
        effect :: Effect2 a (bound at redux.hs:29:44)
        runEffect2 :: GameState -> Effect2 a -> [GameState]
          (bound at redux.hs:29:1) 
Failed, modules loaded: none.

Does anyone know what I'm doing wrong? I effectively want to be able to expand one GameState into multiple GameStates. Each with an independent StdGen and History for that branch. I have done this by putting everything into the Game record and just using non-monadic functions for the effects. This works and it's pretty straight forward. However, composition of these functions is really annoying because they're acting like state and I need to need to handle it myself. This is what monads are great at so I figured reusing that here would be wise. Sadly the list aspect of it has me really confused.

Answer 1

Firstly, the immediate cause of the error is that the type of runListT is...

GHCi> :t runListT
runListT :: ListT m a -> m [a]

... but you are using it as if it produced a [m a], rather than a m [a]. In other words, the map in the definition of result shouldn't be there.

Secondly, in a monadic stack the inner monads rule over the outer ones. Wrapping, for instance, StateT with ListT results in a garden-variety stateful computation that happens to produce multiple results. We can see that by specialising the type of runListT:

GHCi> :set -XTypeApplications
GHCi> :t runListT @(StateT _ _)
runListT @(StateT _ _) :: ListT (StateT t t1) a -> StateT t t1 [a]

Wrapping ListT with StateT, on the other hand, gives us a computation that produces multiple states as well as results:

GHCi> :t runStateT @_ @(ListT _)
runStateT @_ @(ListT _)
  :: StateT t (ListT t1) a -> t -> ListT t1 (a, t)

That being so, you want to swap the transformers in your stack. If you want to have multiple effects for everything, as you describe, and you don't need IO as your base monad, you don't need ListT at all -- simply put [] at the bottom of the stack.

Thirdly, on a tangential note, avoid the ListT from transformers. It is known to be unlawful, and it has been deprecated in the latest version of transformers. A simple replacement for it is provided by the list-t package. (If, at some point further down the road, you get to make use of the pipes streaming library, you might also find its own version of ListT useful.)