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.
问题:
回答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 T
ransformer. 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.