Could someone walk through how bind in the state monad is implemented ( among other things )?

Question

Despite reading through the really clear explanation in LYAH, and then Haskell Wiki, and some other stuff, I am still confused about how the state monad is implemented. I think I understand what it is though I'm not confident.

So let's say I have some trivial data type:

data Simple a = Top a 
  deriving ( Show )

And this:

newtype SimpleState a = SimpleState { applySimple :: Int -> ( a, Int ) }

I then make SimpleState a monad

instance Monad SimpleState where
    return x = SimpleState $ \s -> ( x, s )
    st >>= g = SimpleState $ \s -> let ( x, s' ) = applySimple st s in applySimple ( g x ) s' 

Question 1: How is the lambda taking in s ( for state ) as a parameter? How is it passed in?

Question 2: if applySimple is taking in one parameter in its function signature, why do I have applySimple st s inside the lambda? Why is applySimpleapplied twice?

Even more confusing, this thing changes the state:

tic :: SimpleState Int
tic = SimpleState $ \s -> ( s, s + 1 ) 

Question 3. What is this? Why is it doing some sort of action on the SimpleState but its signature is not a function?

So now I could pass tic into this function:

incr :: Simple a -> SimpleState ( Simple ( a, Int ) ) 
incr ( Top a ) = do 
  v <- tic
  return ( Top ( a, v ) )

Question 4: could I / how would I use tic with >>= ?

And by using it like so:

applySimple ( incr ( Top 1 ) ) 3

I get this:

(Top (1,3),4)

Again, applySimple is applied to two params, which confuses me.

In summary, I'm getting really hung up on the fact that the constructor SimpleState is taking in a function that takes in in s as a param, and have no idea where it's coming from how it's used in context.

Answer 1

Okay, you've smooshed a bunch of questions into one post...

1. Where does the lambda parameter s come from?

return x = SimpleState $ \s -> ( x, s )

If you look at your constructor, SimpleState, you'll notice that it takes a function of type Int -> (a, Int) as an argument. So the lambda is used in order to give us a function of the correct type. Lambda is just one way of making a function.

The reason that a function is necessary is because only through the function parameter is it possible to access the current state of the state monad.

2. Why does applySimple take two parameters?

That's because it's a field accessor.

data Point = Point { x :: Int, y :: Int }

What is the type of x? Well, it's Point -> Int. It extracts a field from a Point value.

origin = Point 0 0
potOfGold = Point 15 3

main = putStrLn $ "Pot of gold is at (" ++ show (x potOfGold) ++ ", " ++
                  show (y potOfGold) ++ ")"

Clearly, x does not have type Int because it is different for each Point. Likewise,

newtype MyState a = MyState { runState :: Int -> (a, Int) }

What is the type of runState? Well, it's MyState -> Int -> (a, Int). It extracts a field (the only field) from a MyState a value.

Why is tic not a function?

Monadic actions do not need to be functions. For example, think about the code putStrLn:

main = putStrLn "Hello, world."

It makes sense to you that putStrLn does something because it is a function, right? Well, you are right that it does something but your reasoning is wrong. You are using imperative intuition for a functional language. Strictly speaking, putStrLn does NOT print anything, it is a function that returns a monadic action, and the resulting monadic action prints "Hello, world.".

printHello :: IO ()
printHello = putStrLn "Hello, world."

Obviously, this does something. It is not a function since it does not take parameters. Get this through your head if you want to understand Haskell: "do something" is a property of monadic actions and it has nothing to do with functions.

4. Could I / how would I use tic with >>= ?

"How do I use feature X with feature Y" is near the top of my list of pet peeves, as far as questions on Stack Overflow are concerned. It's like asking "how do I use water in the kitchen" and I say "you could mop the floor" but really you were thirsty and wanted to drink the water. Better to ask a question like, "How do I use water to clean the floor?" or "How do I use water to quench my thirst?" These questions are answerable.

So, the answer to question 4 is "Yes, you can use tic with >>=." And, "How you use it depends on what you want to do."

Footnote: I suggest that you conform to predominant coding styles, e.g., f (x y) instead of f ( x y ), since it will help people read your code.

Answer 2

Question 1: How is the lambda taking in s ( for state ) as a parameter? How is it passed in?

Let's use the classic definitions of get and put, defined as:

put :: Int -> SimpleState ()
put n = SimpleState (\_ -> ((), n))

get :: SimpleState Int
get = SimpleState (\s -> (s, s))

When you call applySimple, you unwrap the SimpleState, which exposes a function of type Int -> (a, Int). Then you apply that function to your initial state. Let's try it out using some concrete examples.

First, we'll run the command put 1, with an initial state of 0:

applySimple (put 1) 0

-- Substitute in definition of 'put'
= applySimple (SimpleState (\_ -> ((), 1))) 0

-- applySimple (Simple f) = f
(\_ -> ((), 1)) 0

-- Apply the function
= ((), 1)

Notice how put ignores the initial state and just replaces the right state slot with 1, leaving behind () in the left return value slot.

Now let's try running the get command, using a starting state of 0:

applySimple get 0

-- Substitute in definition of 'get'
= applySimple (SimpleState (\s -> (s, s))) 0

-- applySimple (SimpleState f) = f
= (\s -> (s, s)) 0

-- Apply the function
= (0, 0)

get just copies 0 into the left return value slot, leaving the right state slot unchanged.

So the way you pass your initial state into that lambda function is just by unwrapping the SimpleState newtype to expose the underlying lambda function and directly applying the lambda function to the initial state.

Question 2: if applySimple is taking in one parameter in its function signature, why do I have applySimple st s inside the lambda? Why is applySimpleapplied twice?

That's because applySimple's type is not Int -> (a, Int). It's actually:

applySimple :: SimpleState -> Int -> (a, Int)

This is a confusing aspect of Haskell's record syntax. Whenever you have a record field like:

data SomeType { field :: FieldType }

... then field's type is actually:

field :: SomeType -> FieldType

I know it's weird.

Question 3. What is this? Why is it doing some sort of action on the SimpleState but its signature is not a function?

The SimpleState newtype hides the function that it wraps. newtypes can hide absolutely anything until you unwrap them. Your SimpleState does have function inside of it, but all the compiler sees is the outer newtype until you unwrap it with applySimple.

Question 4: could I / how would I use tic with >>= ?

You're making a mistake in your definition of incr. The correct way to use tic would be like this:

ticTwice :: SimpleState ()
ticTwice = do
    tic
    tic

... which the compiler translates to:

ticTwice =
    tic >>= \_ ->
    tic

Using your definition of (>>=) and tic, you can prove that this increments the value by two:

tic >>= \_ -> tic

-- Substitute in definition of `(>>=)`
SimpleState (\s ->
    let (x, s') = applySimple tic s
    in  applySimple ((\_ -> tic) x) s')

-- Apply the (\_ -> tic) function
SimpleState (\s ->
    let (x, s') = applySimple tic s
    in  applySimple tic s')

-- Substitute in definition of `tic`
SimpleState (\s ->
    let (x, s') = applySimple (SimpleState (\s -> (s, s + 1))) s
    in  applySimple (SimpleState (\s -> (s, s + 1))) s'

-- applySimple (SimpleState f) = f
SimpleState (\s ->
    let (x, s') = (\s -> (s, s + 1)) s
    in  (\s -> (s, s + 1)) s'

-- Apply both functions
SimpleState (\s ->
    let (x, s') = (s, s + 1)
    in  (s', s' + 1)

-- Simplify by getting rid of unused 'x'
SimpleState (\s ->
    let s' = s + 1
    in  (s', s' + 1)

-- Simplify some more:
SimpleState (\s -> s + 1, s + 2)

So you see that when you chain two tics using (>>=), it combines them into a single stateful function that increments the state by 2, and returns the state plus 1.