Revisiting pattern match overlap checks in Haskell
summary
GHC pattern-match coverage and overlap checks get refactored by desugaring complex patterns into a linear sequence of simple guards and building a fact base (Delta) of refinements that represents sets of values. The compiler computes which values fall through each clause, emits concrete counterexample values, and handles GADTs, pattern guards, strict constructors and pattern synonyms. The previous algorithm is slow and can be exponential so the implementation uses throttling, and the new modular refactor is implemented in GHC and improves correctness and performance.
AI-written summary · about
chapters (8)
- 0:00Start
- 0:58Datatype Declarations
- 4:26Laziness
- 12:32Strict Patterns
- 16:36Pattern Guards
- 17:34Long Distance Information
- 35:25Refinement Types
- 43:43Coffee Break
related talks
23mHigher order Patterns in Rewrite Rules
01h 26mImplementing Dependent Pattern Matching and Type Unification Part 2
26mEmbedded Pattern Matching
01h 38mGHC Core Optimisations
01h 37mGHC's Renamer
49mMaking sense of the Haskell type system
28mDesign Patterns for Parser Combinators (Functional Pearl)
40mWhat Haskell taught us when we were not looking