CODEWITHSUNDEEP
haskellmonadsstate-monad
dimid
dimid

Reputation: 7631

understanding StateMonad

I'm a haskell beginner and trying to understand this definition of a StateMonad, specifically the bind operation. It's taken from Generalising Monads to Arrows page 4.

instance Monad (StateMonad s) where
     return a = SM (\s -> (a, s))
     x >>= f = SM (\s -> let
                             SM x' = x
                             (a, s') = x' s
                             SM f' = f a
                             (b, s'') = f' s'
                         in (b, s''))

Upvotes: 3

Views: 291

Answers (2)

liminalisht
liminalisht

Reputation: 1253

A slightly shorter answer to complement Cirdec's...

First, recall that in x >>= f, x is a state monad, f is a fn that returns a state monad, and x >>= f is also a state monad.

The basic idea is as follows. Given some current state s (that will be supplied later when we run the state monad represented by x >>= f), we first want to run x with s, which will yield some value a, along with a new state s'. Then we want to run f a, which gives us another state monad. We don't just want to run this resulting state monad f a with any state though; rather, we want to run it with the state that resulted from x, namely s', giving us some new value b and some new state s''. x >>= f will represent this computation from s -> (b, s'').

Remember: the whole point of using a state monad is to avoid explicitly passing state along as another parameter to all of our functions (that would get really messy, really quickly). So the idea here is to have the state threaded through properly behind the scenes whenever we bind actions to a state monad.

To do this, we (1) pattern match on x to get the fn inside, then (2) run this function with the current state s to get a result a and some new state s'. Then we (3) compute f a, which returns a state monad, and pattern match on this monad to get the fn inside; then (4) run the fn with the state s' to get a value b and some final state s''. (1) through (4) correspond to the four lines immediately following let in your code. What do you know, we've just defined a fn from s to (b, s''), which properly passes along state behind the scenes. Now we'll just wrap that in a constructor and we're done. x >>= f now represents a computation that we can run later by supplying an initial state.

Upvotes: 1

Cirdec
Cirdec

Reputation: 24156

First you need to understand the type of >>=; I'll assume you do since it's on page 2 of that paper and you got past that.

The definition for bind may be easier to understand if we define runState. 

newtype SM s a = SM (s -> (a, s))

runState ::  SM a  -> s -> (a, s)
runState    (SM f)    s =  f s
-- this is equivalent to
-- runState (SM f) =  f

runState runs a state monad by extracting the function f that transforms the state and applying it to the initial state s. The function f returns a tuple of type (a, s). The tuple contains the value (of type a) that depended on the state, and a new state (of type s). The following are equivalent

let (a, s') = runState x s
in ...

let SM x' = x
    (a, s') = x' s
in ...

Both of these extract the function x' for how the state is transformed from x, then apply it to an initial state s. The resulting tuple (a, s') holds the state-dependent value a, and the new state s'.

We can replace the SM pattern matching in the definition of >>= with runState.

 x >>= f = SM (\s -> let
                         (a, s')  = runState x     s
                         (b, s'') = runState (f a) s'
                     in  (b, s''))

Now we'll go through it piece by piece.

Bind constructs a new StateMonad with a function that depends on some initial state s. It returns a state-dependent value b and a new state s'':

 x >>= f = SM (\s -> let
                         ...
                     in  (b, s''))

The state-dependent value a and a new state s' are computed by running the state monad x with the initial state s:

                     let
                         (a, s')  = runState x     s

A new state monad f a is determined from the user-supplied function f and the state-dependent value a. This second state monad is run with the intermediate state s'. It computes another state-dependent value b and a final state s''.

                         (b, s'') = runState (f a) s'

The second state-dependent value b and the final state s'' are what's returned by the function constructed for the new StateMonad.

Upvotes: 3

Related Questions