Parser example isn't clicking with me

Question

I'm reading through Real World Haskell, and as an intro into functors/monads, it gives the following example:

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

(The rest of it can be read about a quarter of the way down the page at: http://book.realworldhaskell.org/read/code-case-study-parsing-a-binary-data-format.html)

The thing that doesn't make any sense to me is, why does this function not take any parameters? I'd expect it to accept a Parse object containing the text to be parsed, then return the parsed text, and a new Parse object. Instead, (as I see it) it's "magically" accessing a Parser, popping a byte, then returning a "modified" Parser. Where does the object come from? I've been staring at at for a day now and still have no clue how this function works.

Any guidance here would be appreciated.

Answer 1

The Parse type is defined as

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

So if you're wondering where the input comes from, it's in the definition of the type! Each Parse value wraps up a function, and then we use ==> in this example to chain two Parses together through composition into a new Parse. This is then finally run using runParse. This function requires a ParseState, being defined as

data ParseState = ParseState
    { string :: L.ByteString
    , offset :: Int64
    } deriving (Show)

this is what carries the string being parsed.

You can think of the Parse type as an alias for the type

ParseState -> Either String (a, ParseState)

which is a function like you'd expect. With the ==> function having the type (with the newtype wrapper removed)

(==>)
    ::       (ParseState -> Either String (a, ParseState))
    -> (a -> (ParseState -> Either String (b, ParseState)))
    ->       (ParseState -> Either String (b, ParseState))

we can then take one Parse and feed it into another Parse to make a new Parse. All of this is no more than a fancy wrapper around regular function composition. It gets it input from where-ever runParse is called from the initial state.