Category Theory Key idea: A parser is just a function from a string to a value and whatever's left over — and building bigger parsers out of smaller ones turns out to be exactly what Applicative was for all along

Parser Combinators: Applicative, Earning Its Keep

One of Haskell's most satisfying 'oh, THAT'S what Applicative is for' moments: a tiny parsing library, built entirely from Functor, Applicative, and Alternative, with no new machinery invented along the way — the direct ancestor of Megaparsec and Parsec.

What a parser actually is

Strip away everything incidental, and a parser is one specific kind of function: given some input text, it either fails, or succeeds with a parsed value and whatever input is left over for the next parser to work on.

newtype Parser a = Parser { runParser :: String -> Maybe (a, String) }

That’s the entire foundation — a function from String to Maybe (a, String). Nothing means failure; Just (value, rest) means success, with rest being exactly the part of the input this parser didn’t consume. Everything else in this chapter is built by combining values of this one type.

charP :: Char -> Parser Char
charP c = Parser f
  where
    f (x:xs) | x == c = Just (c, xs)
    f _               = Nothing

ghci> runParser (charP '3') "3,4"
Just ('3',",4")

charP '3' succeeds only if the input starts with '3', consuming exactly that one character and leaving the rest untouched.

Functor: transforming what a parser produces

fmap for Parser should transform the parsed value, without touching how much input gets consumed or whether the parse succeeds at all:

instance Functor Parser where
  fmap f (Parser p) = Parser $ \input -> do
    (a, rest) <- p input
    return (f a, rest)

The do block here is Maybe’s own Monad instance (Chapter 11) doing the heavy lifting — if p input fails, the whole thing short-circuits to Nothing automatically; only on success does f get applied to the parsed value, with rest passed through unchanged.

Applicative: this is the payoff

Here’s where parser combinators earn the name. Parsing “this, then that, then combine the two results” is exactly the shape <*> was built for (Chapter 10) — and once Applicative is defined, sequencing parsers stops requiring any new machinery at all:

instance Applicative Parser where
  pure a = Parser $ \input -> Just (a, input)
  (Parser pf) <*> (Parser pa) = Parser $ \input -> do
    (f, rest1) <- pf input
    (a, rest2) <- pa rest1
    return (f a, rest2)

pure a is a parser that consumes nothing and always succeeds with a — the identity Chapter 10 already required. <*> runs the first parser, threads whatever input is left to the second parser, and combines both results with ordinary function application — precisely the “run these in sequence, then combine” pattern from Chapter 10, now doing real work.

import Data.Char (isDigit)

spanP :: (Char -> Bool) -> Parser String
spanP pred = Parser $ \input ->
  let (matched, rest) = span pred input
  in Just (matched, rest)

intP :: Parser Int
intP = Parser $ \input ->
  case runParser (spanP isDigit) input of
    Just (digits, rest) | not (null digits) -> Just (read digits, rest)
    _ -> Nothing

data Point = Point Int Int deriving Show

pointP :: Parser Point
pointP = Point <$> intP <* charP ',' <*> intP

ghci> runParser pointP "3,4"
Just (Point 3 4,"")
Parsing '3,4' step by step: intP consumes 3, charP consumes the comma, intP consumes 4, combined into Point 3 4

Figure: Each combinator consumes a prefix of the input and threads the remainder to the next step — exactly the “do this, then that, then combine the results” shape Applicative gives for free.

Read pointP the way it’s written: “parse an Int, then a comma (whose value is discarded — that’s what <* means, run both but keep only the left result), then another Int, and combine the two Ints with Point.” Point <$> intP partially applies Point to the first parsed integer inside the parser context, and the final <*> supplies the second — <* and *> aren’t new concepts either; they come free from Applicative’s default methods the moment pure and <*> are defined.

Alternative: trying one parser, then another

Real parsers need choice — try this, and if it fails, try that instead. Alternative (built on Applicative) provides exactly this, and Parser’s instance can lean entirely on Maybe’s own:

import Control.Applicative

instance Alternative Parser where
  empty = Parser $ const Nothing
  (Parser p1) <|> (Parser p2) = Parser $ \input -> p1 input <|> p2 input

digitOrLetter :: Parser Char
digitOrLetter = charP 'x' <|> charP 'y'

ghci> runParser digitOrLetter "y5"
Just ('y',"5")

p1 input <|> p2 input reuses Maybe’s own Alternative instance (try the left Maybe, fall back to the right one if it’s Nothing) — Parser’s choice operator is built directly on top of Maybe’s, with no new logic to write.

⚠Common Pitfall

This Parser type backtracks by construction — if p1 fails partway through consuming input, p1 input <|> p2 input tries p2 from the original input, not from wherever p1 gave up. That is exactly right for small examples like this chapter’s, but real-world parsers over large inputs pay a real performance cost for unlimited backtracking; production libraries offer explicit control over exactly when to commit to a parse and stop backtracking, precisely to avoid that cost at scale.

In the Wild

Megaparsec and its predecessor Parsec are the production versions of exactly this idea — vastly more sophisticated (detailed error messages with source positions, explicit backtracking control, streaming input) but built on the same Functor/Applicative/Alternative foundation this chapter just derived by hand. Parser combinators are also one of Haskell’s clearest cross-language exports: Rust’s nom, Scala’s fastparse, and Swift’s swift-parsing all use the identical combinator style, applying small parsers to build up larger ones compositionally rather than hand-writing a monolithic parsing function.

λA Category-Theoretic View

Parser’s Applicative instance is a genuine instance of the same abstraction Chapter 10 introduced — pure and <*> satisfy the same laws every other Applicative in this book has satisfied, which is precisely why <$>, <*>, and <* compose here exactly the way they did for Maybe or lists, with no special-casing. The payoff of learning Applicative once, abstractly, is that an entire parsing library falls out of it with almost no additional design work — the interface was already general enough.

Every chapter from Functors onward asked you to trust that these abstractions would eventually pay for themselves. Parser combinators are as direct a payoff as Haskell offers: the exact same <*> that combined two Maybes or zipped two lists together, reused without modification, is enough to build a real, working parsing library from four small pieces and about twenty lines of instance code.