Design Patterns for Parser Combinators (Functional Pearl)
summary
A cookbook of concrete parser-combinator fixes demonstrates on a small calculator parser: left recursion is eliminated by replacing naive recursion with chainL and chainR style combinators; whitespace is handled by a lexeme/token/fully layering; keyword collisions are solved with a keyword combinator that rejects identifier prefixes; a weak AST is replaced by a strong AST and typed infix folds (b->a->b) to force correct associativity. Patches land, CI tests pass, and the patterns appear in an accepted Haskell Symposium paper.
AI-written summary · about
chapters (17)
- 0:00Intro
- 1:10The Problem
- 1:30Code Review
- 2:00Pull Request
- 2:30Reviewing the Commit
- 3:45Recursive Descent
- 5:00Chain Combinators
- 5:45Chain R
- 6:30Why Parser Combinators
- 7:05Failed
- 9:45More Failure
- 11:45Check CI
- 12:25Weak vs Strong
- 13:45Commit error
- 16:30Possible improvements
- 17:55Reviewing the code
- 20:50Questions
related talks
38mRefactoring Recursion
01h 26mImplementing Dependent Pattern Matching and Type Unification Part 2
26mEmbedded Pattern Matching
44mRevisiting pattern match overlap checks in Haskell
23mHigher order Patterns in Rewrite Rules
01h 38mGHC Core Optimisations
01h 07mHaskell The Legend of DSLs
03h 04mHaskell for Beginners: Learn Functional Programming from Scratch