Pattern matching: Difference between revisions

Revision as of 03:15, 5 November 2023

Revision as of 01:37, 26 January 2024

Line 7:

Sequence patterns (e.g., a text string) are often described using [[regular expression]]s and matched using techniques such as [[backtracking]].

Tree patterns are used in some [[programming language]]s as a general tool to process data based on its structure, e.g. [[C Sharp (programming language)|C#]],<ref>{{cite web|url=https://docs.microsoft.com/en-us/dotnet/csharp/pattern-matching|title=Pattern Matching - C# Guide}}</ref> [[F Sharp (programming language)|F#]],<ref>{{cite web|url=https://docs.microsoft.com/en-us/dotnet/fsharp/language-reference/pattern-matching|title=Pattern Matching - F# Guide}}</ref> [[Haskell (programming language)|Haskell]],<ref>[http://www.haskell.org/tutorial/patterns.html A Gentle Introduction to Haskell: Patterns]</ref> [[ML (programming language)|ML]], [[Python (programming language)|Python]],<ref>{{Cite web|title=What's New In Python 3.10 — Python 3.10.0b3 documentation|url=https://docs.python.org/3.10/whatsnew/3.10.html#pep-634-structural-pattern-matching|access-date=2021-07-06|website=docs.python.org}}</ref> [[Ruby (programming language)|Ruby]],<ref>{{Cite web|title=pattern_matching - Documentation for Ruby 3.0.0|url=https://docs.ruby-lang.org/en/3.0.0/doc/syntax/pattern_matching_rdoc.html|access-date=2021-07-06|website=docs.ruby-lang.org}}</ref> [[Rust (programming language)|Rust]],<ref>{{cite web |url=https://doc.rust-lang.org/book/ch18-03-pattern-syntax.html |title=Pattern Syntax - The Rust Programming languageLanguage}}</ref> [[Scala (programming language)|Scala]],<ref>{{Cite web|title=Pattern Matching|url=https://docs.scala-lang.org/tour/pattern-matching.html|access-date=2021-01-17|website=Scala Documentation}}</ref> [[Swift (programming language)|Swift]]<ref>{{cite web|url=https://docs.swift.org/swift-book/ReferenceManual/Patterns.html|title=Patterns — The Swift Programming Language (Swift 5.1)}}</ref> and the symbolic mathematics language [[Mathematica]] have special [[Syntax (programming languages)|syntax]] for expressing tree patterns and a [[language construct]] for [[Conditional (computer programming)|conditional execution]] and value retrieval based on it.

Often it is possible to give alternative patterns that are tried one by one, which yields a powerful [[Conditional (programming)|conditional programming construct]]. Pattern matching sometimes includes support for [[guardGuard (computingcomputer science)|guards]].{{citation needed|date=January 2019}}

==History==

{{See also|Regular expression#History}}

{{Expand section|date=May 2008}}

Early programming languages with pattern matching constructs include [[COMIT]] (1957), [[SNOBOL]] (1962), [[Refal]] (1968) with tree-based pattern matching, [[Prolog]] (1972), St Andrews Static Language ([[SASL (programming language)|SASL]]) (1976), [[NPL (programming language)|NPL]] (1977), and [[Kent Recursive Calculator|KRC]] (KRC) (1981).

Many [[text editor]]s support pattern matching of various kinds: the [[QED (text editor)|QED editor]] supports [[regular expression]] search, and some versions of [[TECO (text editor)|TECO]] support the OR operator in searches.

Line 33:

</syntaxhighlight>

Here, the first <code>n</code> is a single variable pattern, which will match absolutely any argument and bind it to name n to be used in the rest of the definition. In Haskell (unlike at least [[Hope (programming language)|Hope]]), patterns are tried in order so the first definition still applies in the very specific case of the input being 0, while for any other argument the function returns <code>n * f (n-1)</code> with n being the argument.

The wildcard pattern (often written as <code>_</code>) is also simple: like a variable name, it matches any value, but does not bind the value to any name. Algorithms for [[matching wildcards]] in simple string-matching situations have been developed in a number of [[recursion|recursive]] and non-recursive varieties.<ref>{{cite web| last=Cantatore| first=Alessandro| title=Wildcard matching algorithms| year=2003| url=http://xoomer.virgilio.it/acantato/dev/wildcard/wildmatch.html}}</ref>

Line 65:

The creations of these functions can be automated by Haskell's data [[Record (computer science)|record]] syntax.

This [[OcamlOCaml]] example which defines a [[Red–black tree|red-blackred–black tree]] and a function to re-balance it after element insertion shows how to match on a more complex structure generated by a recursive data type. The compiler verifies at compile-time that the list of cases is exhaustive and none are redundant.

<syntaxhighlight lang="ocaml">

Line 91:

==Pattern matching in Mathematica==

In [[Mathematica]], the only structure that exists is the [[Tree (data structure)|tree]], which is populated by symbols. In the [[Haskell (programming language)|Haskell]] syntax used thus far, this could be defined as

<syntaxhighlight lang="haskell">

data SymbolTree = Symbol String [SymbolTree]

Line 149:

</syntaxhighlight>

Mailboxes in [[Erlang (programming language)|Erlang]] also work this way.

The [[Curry–Howard correspondence]] between proofs and programs relates [[ML (programming language)|ML]]-style pattern matching to [[Proof by cases|case analysis]] and [[proof by exhaustion]].

Line 161:

In Mathematica, strings are represented as trees of root StringExpression and all the characters in order as children of the root. Thus, to match "any amount of trailing characters", a new wildcard ___ is needed in contrast to _ that would match only a single character.

In Haskell and [[functional programming]] languages in general, strings are represented as functional [[List (computing)|lists]] of characters. A functional list is defined as an empty list, or an element constructed on an existing list. In Haskell syntax:

<syntaxhighlight lang="haskell">

Line 205:

will match a string that consists of a letter first, and then a number.

In Haskell, [[guardGuard (computingcomputer science)|guards]] could be used to achieve the same matches:

<syntaxhighlight lang="haskell">

Line 215:

===SNOBOL===

{{Main|SNOBOL}}

SNOBOL (''StriNg Oriented and symBOlic Language'') is a computer programming language developed between 1962 and 1967 at [[AT&T Corporation|AT&T]] [[Bell Laboratories]] by [[David J. Farber]], [[Ralph E. Griswold]] and [[Ivan P. Polonsky]].

Line 225 ⟶ 224:

==See also==

* [[Artificial Intelligence Markup Language|AIML]] (AIML) for an AI language based on matching patterns in speech

* [[AWK|AWK language]] language

* [[Coccinelle (software)|Coccinelle]] pattern matches C source code

* [[Matching wildcards]]

Line 255 ⟶ 254:

*[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

*[http://www.cs.cornell.edu/Projects/jmatch JMatch]: the [[Java (programming language)|Java programming]] 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

Line 266 ⟶ 265:

*[http://www.datamystic.com/easypatterns_reference.html EasyPattern language] pattern matching language for non-programmers

{{Strings |state=collapsed}}

{{Authority control}}