haskell - How do more recent updates in the state monad not get replaced by earlier ones? - Stack Overflow

admin管理员组

文章数量:1349699

Here's the definition of the state monad from chapter 13 of Learn You a Haskell

instance Monad (State s) where
    return x = State $ \s -> (x,s)
    (State h) >>= f = State $ \s -> let (a, newState) = h s
                                        (State g) = f a
                                    in  g newState

Based on this definition, it looks to me as though the state in the tuple returned by f a will be replaced by newState even though it's the more recent version. To take a specific example from Real World Haskell chapter 10 where this is clearly not what the authors intend (note the use of ==> instead of >>= because they haven't yet formally introduced monads)

parseByte :: Parse Word8
parseByte =
    getState ==> \initState ->
    case L.uncons (string initState) of
      Nothing ->
          bail "no more input"
      Just (byte,remainder) ->
          putState newState ==> \_ ->
          identity byte
        where newState = initState { string = remainder,
                                     offset = newOffset }
              newOffset = offset initState + 1

Where

newtype Parse a = Parse {
      runParse :: ParseState -> Either String (a, ParseState)
    }

identity :: a -> Parse a
identity a = Parse (\s -> Right (a, s))
 
(==>) :: Parse a -> (a -> Parse b) -> Parse b
firstParser ==> secondParser  =  Parse chainedParser
  where chainedParser initState   =
          case runParse firstParser initState of
            Left errMessage ->
                Left errMessage
            Right (firstResult, newState) ->
                runParse (secondParser firstResult) newState

In parseByte, I don't see how initState doesn't replace newState.

Here's the definition of the state monad from chapter 13 of Learn You a Haskell

instance Monad (State s) where
    return x = State $ \s -> (x,s)
    (State h) >>= f = State $ \s -> let (a, newState) = h s
                                        (State g) = f a
                                    in  g newState

Based on this definition, it looks to me as though the state in the tuple returned by f a will be replaced by newState even though it's the more recent version. To take a specific example from Real World Haskell chapter 10 where this is clearly not what the authors intend (note the use of ==> instead of >>= because they haven't yet formally introduced monads)

parseByte :: Parse Word8
parseByte =
    getState ==> \initState ->
    case L.uncons (string initState) of
      Nothing ->
          bail "no more input"
      Just (byte,remainder) ->
          putState newState ==> \_ ->
          identity byte
        where newState = initState { string = remainder,
                                     offset = newOffset }
              newOffset = offset initState + 1

Where

newtype Parse a = Parse {
      runParse :: ParseState -> Either String (a, ParseState)
    }

identity :: a -> Parse a
identity a = Parse (\s -> Right (a, s))
 
(==>) :: Parse a -> (a -> Parse b) -> Parse b
firstParser ==> secondParser  =  Parse chainedParser
  where chainedParser initState   =
          case runParse firstParser initState of
            Left errMessage ->
                Left errMessage
            Right (firstResult, newState) ->
                runParse (secondParser firstResult) newState

In parseByte, I don't see how initState doesn't replace newState.

• haskell
• state-monad

Share Improve this question Follow edited yesterday David Young 10.8k22 gold badges3434 silver badges4747 bronze badges asked Apr 2 at 0:29 planarianplanarian 2,1831818 silver badges1919 bronze badges

Add a comment  | 

1 Answer 1

Sorted by: Reset to default 5

Take another look at the definition:

(State h) >>= f = State $ \s -> let (a, newState) = h s
                                    (State g) = f a
                                in  g newState

The g newState call does not set the final state to newState. It passes the newState to the second g operation as its starting state. If g changes the state, the final state of the combined operation will be a new, unnamed state returned by the g call.

It may help to rename some variables and giving a temporary name to the return value from the g call. By doing this, you can write this as the functionally identical implementation:

(State op1) >>= f = State $ \firstState -> let (a, secondState) = op1 firstState
                                               (State op2) = f a
                                               (b, thirdState) = op2 secondState
                                           in (b, thirdState)

Does this help explain what's going on? On the right-hand side of this definition, the composite operation that's constructed applies the first operation op1 :: s -> (a, s) which takes the FIRST state and produces a value of type a and a SECOND state. Then, the value of type a can be passed to f to calculate the second operation op2 :: s -> (b, s). Then, this operation is passed the SECOND state and produces a value of type b and a THIRD state. So, the final state will be the THIRD state, after it has been transformed by both operations, in order.

The idea is the same for ==>. The initState is passed to the chainedParser, but the way the chainedParser works is that it applies the firstParser to that initState, getting a newState, and then it passes that newState to the secondParser, which when it is run by runParser will return an unnamed, final state. So, initState and newState are the starting and ending state respectively of firstParser, and newState and some "unnamed state" are the starting and ending state respectively of secondParser.

本文标签： haskellHow do more recent updates in the state monad not get replaced by earlier onesStack Overflow