Parsing
Before we dive into parser combinators, let’s briefly review what parsing is, and consider some alternative options for obtaining Haskell parsers.
What is parsing?
The basic idea of parsing is to take a string representation of some data and turn it into the corresponding value of a structured data type. For example, consider the "1 + 2" string. With a parser, we could turn this into a value, Plus (Lit 1) (Lit 2), of the Expr algebraic data type:
data Expr = Lit Int | Plus Expr Expr
Typically, the textual value is convenient for humans, but further programmatic processing is much easier on the structured value. For example, it is much easier to write an evaluation function that takes Expr than a string.
Because the string can easily be ill-formed – for example, "1 +" or "1 ++ 2" – parsing is an operation that may fail. We model this in Haskell with the result type, Maybe Expr. Thus, the basic parsing interface...
