Pattern Matching

Pattern Matching (English for pattern matching ) or pattern- based search is a term used for symbol-processing method that identify discrete structures, or subsets of a discrete structure on the basis of a predetermined pattern.

Basics

A discrete structure consists of discrete elements ( symbols) and relations between them. Examples are strings, but also trees or graphs. The pattern itself is also a discrete structure, but can be described by using additional metacharacters a whole class of structures. In contrast to the pattern recognition for interpreting continuous structures, operates the pattern matching from the beginning on a symbolic representation.

However, the pattern matching plays a central role not only in search but also in the pattern and rule-based transformation of discrete structures. In replacement - or transformation systems, the pattern matching is the first step. Parts of the pattern are identified with parts of the analyzed structure. Found partial structures go then as a parameter in the transformation function. Examples of such transformations are replacing text in strings and graph rewriting systems.

Areas of application

Programming

In some functional or logical programming languages ​​, it is used to process data according to their structure. (Eg: Scala, Objective CAML, ML, Haskell, Erlang )

Example: In the functional programming language Haskell, the arguments are matched in a function definition with patterns. A pattern can either describe each value of a data type, a primitive value or a data constructor.

- Matcht the empty list ( Constructor []) f [ ] = ... - Matcht all lists of length> 0 ( :) constructor, where x is the head and xs contains the list of remaining f (x: xs ) = ... word processing

It is also used to edit text. In programming languages ​​such as Perl or awk, and also in most text editors tools exist to search a text for a pattern. The patterns consist of regular expressions. See string - matching algorithm