Pattern matching

from Wikipedia, the free encyclopedia

Pattern Matching (English for pattern matching ) or pattern-based search is a term for symbol processing procedures based on a predetermined pattern, the search mask , discrete identify a discrete structure or structures subsets.

Pattern matching is, for example, a method of phylogenetic analysis in bioinformatics .


A discrete structure consists of discrete elements ( symbols ) and relationships between them. Examples are strings , but also trees or graphs . The search pattern itself is also a discrete structure, but it can describe a whole class of structures by using additional metacharacters . In contrast to pattern recognition , which interprets continuous structures, pattern matching operates from the outset on a symbolic representation.

Pattern matching does not only play a central role in the search, but also in the pattern and rule-based transformation of discrete structures. Pattern matching is the first step in replacement or transformation systems . Parts of the pattern are identified with parts of the analyzed structure. The sub-structures found are then used as parameters in the transformation function. Examples of such transformations are text replacement into character strings and graph replacement systems .

application areas


In some functional or logical programming languages, pattern matching is used to process data based on its structure (e.g. Scala , Objective CAML , ML , Haskell , Erlang , Opal )

Example case distinction: A possible definition of the nth Fibonacci number is:

This definition can be transferred directly to Haskell with the help of pattern matching .

-- Matcht die ersten beiden Fälle
fib 0 = 0
fib 1 = 1
-- Alle anderen Zahlen n sind definiert als
fib n = fib(n-1) + fib(n-2)

Example: In Haskell, the arguments in a function definition are matched with patterns. A pattern can, but does not have to be an elementary value (e.g. 0), as in the previous example, but can also describe a data constructor.

-- matcht die leere Liste (Konstruktor [])
f [] = ...
-- matcht alle Listen der Länge > 0 (Konstruktor :), wobei x den Kopf und xs den Listenrest enthält
f (x:xs) = ...

Word processing

Pattern matching is also used to manipulate text. In programming languages ​​such as Perl or awk and also in most text editors there are tools to search a text for a pattern. The patterns consist of regular expressions .

See also