Stuck in the State Monad

Question

I want to create a graph structure using an IntMap of nodes and unique keys. This topic has been covered well here and here. I understand how the state monad works by basically wrapping a function of state -> (val,state) in a newtype so we can create a monad instance for it. I have read about the topic quite a bit. I still cant seem to get my head around how I can get unique (or just incremental) values throughout the execution of my program. It's easy enough to get a run of successive IDs, but once I "runState" to get out of the monad it seems like I'm back where I started with having to keep track of the current ID. I feel like I'm stuck in the monad. The other option I considered was to keep the entire IntMap and current "next" ID as the state, but that seems very "imperative" and extreme. This question is very similar but did not get many answers(or maybe I'm just missing something obvious). What is the idiomatic way to utilize the state monad to get unique ID throughout a program execution? Thanks.

Answer 1

Let's imagine we were to IO-ify the State monad. What would that look like? Our pure State monad is just a newtype around:

s -> (a, s)

Well, the IO version might do a little bit of side effects before returning the final values, which would look like:

s -> IO (a, s)

That pattern is so common it has a name, specifically StateT:

newtype StateT s m a = StateT { runStateT :: s -> m (a, s) }

The name has a T at the end because it is a monad Transformer. We call m the "base monad" and StateT s m the "transformed" monad.

StateT s m is only a Monad if m is a Monad:

instance (Monad m) => Monad (StateT s m) where {- great exercise -}

However, in addition to that, all monad transformers implement the MonadTrans class, defined as follows:

class MonadTrans t where
    lift :: (Monad m) => m a -> t m a

instance MonadTrans (StateT s) where {- great exercise -}

If t is StateT s, then lift's type specializes to:

lift :: m a -> StateT s m a

In other words, it lets us "lift" an action in the base monad to become an action in the transformed monad.

So, for your specific problem, you want the StateT (IntMap k v) IO monad, which extends IO with additional State. Then you can write your entire program in this monad:

main = flip runStateT (initialState :: IntMap k v) $ do
    m <- get        -- retrieve the map
    lift $ print m  -- lift an IO action
    (k, v) <- lift readLn
    put (insert k v m)

Notice that I still use get and put. That's because the transformers package implements all the concepts I described and it generalizes the signatures of get and put to be:

get :: (Monad m) => StateT s m s
put :: (Monad m) => s -> StateT s m ()

That means they automatically work within StateT. transformers then just defines State as:

type State s = StateT s Identity

That means that you can use get and put for both State and StateT.

To learn more about monad transformers, I highly recommend Monad Transformers - Step by Step.