Pattern Matching
Subject: Computer and Technology noun /ˈpæt.ərn ˌmætʃ.ɪŋ/ 1 definition
- computer-science
- programming-languages
- functional-programming
- algorithms
-
Definition (noun)
Entry #262 · UpdatedPattern Matching is a deterministic computational technique for checking whether a given sequence of tokens, data structure, or expression conforms to the shape and constraints of a formal template. During evaluation, an engine or compiler tests the input against candidate patterns—composed of literals, wildcards, type constructors, regular expressions, or nested subpatterns—and, upon a match, either locates the target span or destructures and binds inner components to variables. In programming languages and data processing systems, it replaces verbose conditional chains with declarative control flow and enables compilers to verify branch exhaustiveness statically. Unlike statistical pattern recognition in machine learning, which produces probabilistic classifications from noisy inputs, pattern matching enforces exact, rule-driven criteria where an input either strictly satisfies a specification or fails to match.
Common Forms
Structural Pattern Matching: Evaluates the shape, variant tags, and field values of algebraic data types, tuples, or objects—often augmented with boolean guards—to destructure values and select execution arms in languages such as Rust, Haskell, Scala, and Python.
Exact String and Subsequence Matching: Scans linear text or byte streams for literal substrings or dictionaries of keywords without backtracking, typically using deterministic algorithms such as Knuth–Morris–Pratt (KMP), Boyer–Moore, or Aho–Corasick.
Regular Expression Matching: Evaluates character strings against formal patterns built with wildcards, character classes, alternation, and quantifiers using finite-automaton engines (DFA or NFA) or backtracking matchers for validation and extraction.
Tree and Graph Pattern Matching: Compares hierarchical or relational templates against abstract syntax trees (ASTs), symbolic expressions, or property graphs—used in compiler optimization passes, term rewriting, and graph query languages like Cypher and SPARQL.
Example
In a Rust network service, a
matchexpression inspects an incomingPacketenum against patterns such asPacket::Data { stream_id: 1, payload },Packet::Data { stream_id, .. },Packet::Ack(seq), andPacket::Close { code }. When a data packet arrives on stream1, the matcher bindspayloaddirectly for JSON decoding, while the compiler statically verifies that noPacketvariant goes unhandled.