is this piece of haskell code correct, if so why?

Question

the haskell wiki (here : https://wiki.haskell.org/State_Monad ) says the state monad bind operator is defined like this :

(>>=) :: State s a -> (a -> State s b) -> State s b
(act1 >>= fact2) s = runState act2 is 
    where (iv,is) = runState act1 s
          act2 = fact2 iv

however it seems incorrect to me as the result of the bind operator is a function wrapped in a constructor thus cannot be applied (I'm talking about this pattern : (act1 >>= fact2) s)

Answer 1

In short: A State object itself does not encapsulate the state, it encapsulates the change of a state.

Indeed, the State type is defined as:

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

where runState is thus a function that takes a state s, and returns a result a and a new state.

The bind operator (>>=) :: State s a -> (a -> State s b) -> State s b basically "chains" state changes together. It thus takes one state changing function f1 :: s -> (a, s), and a function f2 :: a -> State s b, and thus creates a function g :: s -> (b, s) so to speak that is encapsulated in a State constructor. The second function f2 thus takes an a and returns such state changing function as well.

So the bind operator can be defined as:

(State f1) >>= f2 = State $ \i -> let (y, s) = f1 i in runState (f2 y) s

Here we have i as initial state, and we thus will first "chain" i through the f1 state changer. This returns then a 2-tuple: y is the "result" of that call, and s is the new state, we will then pass the result and the new state to f2. Note that here we do not make state changes at all, we only construct a State object that can do that. We thus postpone the real chaining.

If the State is however defined as above, then the piece of code does not match that definition, it defines it, like @HTWN says, as:

type State s a = s -> (a, s)

In that case, it is correct, given that runState is then the id function, since then:

(>>=) :: State s a -> (a -> State s b) -> State s b
(>>=) act1 fact2 = f
    where f s = act2 is 
              where (iv,is) = act1 s
                    act2 = fact2 iv

In order to make it compatible with our State type, we thus add some logic to unwrap and wrap it in the State data constructor:

(>>=) :: State s a -> (a -> State s b) -> State s b
(>>=) act1 fact2 = State f
    where f s = runState act2 is 
              where (iv,is) = runState act1 s
                    act2 = fact2 iv

then it is indeed correct. The main error is not wrapping it in a State data constructor.