Pattern matching: Difference between revisions

Revision as of 05:00, 9 August 2025

Latest revision as of 16:50, 19 August 2025

(2 intermediate revisions by 2 users not shown)

Line 21:

[[Computer algebra system]]s generally support pattern matching on algebraic expressions.<ref>Joel Moses, "Symbolic Integration", MIT Project MAC MAC-TR-47, December 1967</ref>

Pattern matching has its origins in early computing when text editors began incorporating search and replace functionalities. The introduction of regular expressions by Ken Thompson in the early 1970s at Bell Labs was a significant milestone, enabling complex pattern searches within text.<ref>{{cite book |last=Friedl |first=Jeffrey |title=Mastering Regular Expressions |publisher=O'Reilly Media |year=2006 |isbn=978-0596528126}}</ref>

In 1962, the programming language SNOBOL introduced pattern matching capabilities, primarily aimed at string manipulation tasks.<ref>{{cite book |last=Farber |first=Richard |title=Programming Languages: Principles and Practice |publisher=Addison-Wesley |year=1988 |isbn=978-0201079824}}</ref> This innovation influenced later functional languages like ML and Haskell, which integrated pattern matching into their core syntax for handling data structures and control flow.<ref>{{cite book |last=Hughes |first=John |url=https://www.cs.nott.ac.uk/~pszjh/papers/whyfp.pdf |title=Why Functional Programming Matters |publisher=The Computer Journal |year=1989}}</ref>

The 1980s and 1990s saw pattern matching evolve into a fundamental feature in languages such as OCaml, Erlang, and Scala, providing concise and expressive means to deconstruct data and define functions by cases.<ref>{{cite book |last=Pierce |first=Benjamin C. |title=Types and Programming Languages |publisher=MIT Press |year=2002 |isbn=978-0262162098}}</ref> Its continued development reflects ongoing efforts to balance expressiveness with efficiency in software design.

==Terminology==

Line 52 ⟶ 46:

; [[Name binding|Binding]]

: A way of associating a ''name'' with a portion of the discriminant, so that the name is [[Name binding|bound to]] that portion when the continuation executes. For example, in Rust, <{{code>|2=rust|1=match v { (a, b) => ... }</code> }} expects <code>v</code> to be a pair, and <code>a</code> and <code>b</code> are bindings bringing variables of the same name into scope in the continuation ("<code>...</code>").

; Wildcard

Line 61 ⟶ 55:

; Predicate

: Some pattern languages allow user-defined ''predicate'' functions to be embedded in a pattern. The predicate is applied to the portion of the discriminant corresponding to the position of the predicate in the pattern; if the predicate responds with boolean false, the pattern is considered to have failed. For example, in Racket, the pattern <{{code>|(list (? even?) ...)</code>|rkt}} first expects a list, and then applies the predicate <code>even?</code> to each element; the overall pattern thus succeeds only when the discriminant is a list of even numbers.

; View pattern

Line 67 ⟶ 61:

; Constraint

: Some pattern languages allow direct comparison of portions of the discriminant with previously-computed (or constant) data structures. For example, the pattern <{{code>|1=(== expr)</code>|2=rkt}} in Racket compares the value against the result of evaluating <code>expr</code>. In Erlang, mention of any variable already in scope in a pattern causes it to act as a constraint in this way (instead of as a binding).

; Literal pattern; atomic pattern

Line 320 ⟶ 314:

*[https://archive.today/19990225161739/http://www.haskell.org/development/views.html Views: An Extension to Haskell Pattern Matching]

* Nikolaas N. Oosterhof, Philip K. F. Hölzenspies, and Jan Kuper. [https://web.archive.org/web/20060304053330/http://wwwhome.cs.utwente.nl/~tina/apm/applPatts.pdf Application patterns]. A presentation at Trends in Functional Programming, 2005

*[httphttps://www.cs.cornell.edu/Projects/jmatch JMatch]: the [[Java (programming language)|Java]] language extended with pattern matching

*[https://archive.today/20130630081135/http://www.showtrend.com/ ShowTrend]: Online pattern matching for stock prices

*[https://web.archive.org/web/20060211020429/http://cm.bell-labs.com/cm/cs/who/dmr/qed.html An incomplete history of the QED Text Editor] by [[Dennis Ritchie]] - provides the history of regular expressions in computer programs