Pattern matching

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 .

Basics

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

programming

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:

${\ displaystyle {\ text {fib}} (n) = {\ begin {cases} 0 & {\ text {if}} n = 0 \\ 1 & {\ text {if}} n = 1 \\ {\ text { fib}} (n-1) + {\ text {fib}} (n-2) & {\ text {otherwise}} \ end {cases}}}$

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 .

literature

Simon Peyton Jones (Ed.): Haskell 98 Language and Libraries: The Revised Report . Cambridge University Press, 2003, ISBN 0-521-82614-4 ( HTML version - Section 3.17, HTML version ).
Richard Bird: Introduction to Functional Programming using Haskell . 2nd Edition. Prentice Hall Europe, 1998, ISBN 0-13-484346-0 .