Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Haskell State Monad

Does the put function of the State Monad update the actual state or does it just return a new state with the new value? My question is, can the State Monad be used like a "global variable" in an imperative setting? And does put modify the "global variable"?

My understanding was NO it does NOT modify the initial state, but using the monadic interface we can just pass around the new states b/w computations, leaving the initial state "intact". Is this correct? if not, please correct me.

like image 843
user3169543 Avatar asked Oct 18 '15 04:10

user3169543


2 Answers

There's nothing magical about State. You could implement it like this:

newtype State s a = State {runState :: s -> (a, s)}

That is, a State s a (which we think of as a computation that uses a state of type s to produce a result of type a) is just a function that takes a state and returns a result and a new state. You should attempt to write out the Monad instance and definitions of get and put for this definition. The real definition is more general:

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

This allows state to be added to other monadic computations. It's also possible to define state transformers as "operational monads". Apfelmus has a tutorial on those somewhere.

like image 40
dfeuer Avatar answered Sep 23 '22 21:09

dfeuer


The answer is in the types.

newtype State s a = State {runState :: s -> (a, s)}

Thus, a state is essentially a function that takes one parameter, 's' (which we call the state), and returns a tuple (value, state). The monad is implemented like below

instance Monad (State s) where
  return a = State $ \s -> (a,s)
  (State f) >>= h = State $ \s -> let (a,s') =  f s
                                  in (runState h a) s'

Thus, you have a function that operates on the initial state and spits out a value-state tuple to be processed by the next function in the composition.

Now, put is the following function.

put newState = State $ \s -> ((),newState)

This essentially sets the state that will be passed to the next function in the composition and the downstream function will see the modified state.

In fact, the State monad is completely pure (that is, nothing is being set); only what is passed downstream changes. In other words, the State monad saves you the trouble of carrying around a state explicitly in a pure language like Haskell. In other words, State monad just provides an interface that hides the details of state threading (that's what is called in the WikiBooks and or Learn you a Haskell, I think).

The following shows this in action. You have get, which sets the value field to be the same as the state field (Note that, when I mean setting, I mean the output, not a variable). put gets the state via the value passed to it, increments it and sets the state with this new value.

-- execState :: State s a -> s -> s
let x =  get >>= \x -> put (x+10)
execState x 10

The above outputs 20.

Now, let's do the following.

execState (x >> x) 10

This will give an output of 30. The first x sets the state to 20 via the put. This is now used by the second x. The get at this point sets the state passed it to the value field, which is now 20. Now, our put will get this value, increment it by 10 and set this as the new state.

Thus, you have states in a pure context. Hope this helps.

like image 89
Akaberto Avatar answered Sep 25 '22 21:09

Akaberto