Sequence patterns (e.g., a text string) are often described using regular expressions and matched using techniques such as backtracking.
Tree patterns are used in some programming languages as a general tool to process data based on its structure, e.g. C#,[1] F#,[2] Haskell,[3] Java[4], ML, Python,[5] Ruby,[6] Rust,[7] Scala,[8] Swift[9] and the symbolic mathematics language Mathematica have special syntax for expressing tree patterns and a language construct for 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 construct.
[citation needed] 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) (1976), NPL (1977), and Kent Recursive Calculator (KRC) (1981).
Algorithms for matching wildcards in simple string-matching situations have been developed in a number of recursive and non-recursive varieties.
The difference then is that with variable and wildcard parts, a pattern does not build into a single value, but matches a group of values that are the combination of the concrete elements and the elements that are allowed to vary within the structure of the pattern.
It may help to think of the abstract syntax tree of a programming language and algebraic data types.
This OCaml example which defines a red–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.
For instance, in Haskell a list comprehension could be used for this kind of filtering: evaluates to In Mathematica, the only structure that exists is the tree, which is populated by symbols.
The function Trace can be used to monitor a computation, and return the elements that arise which match a pattern.
A consequence of this is the ability to use patterns to declaratively make statements about pieces of data and to flexibly instruct functions how to operate.
The same pattern in Haskell: Symbolic entities can be introduced to represent many different classes of relevant features of a string.
In Haskell, guards could be used to achieve the same matches: The main advantage of symbolic string manipulation is that it can be completely integrated with the rest of the programming language, rather than being a separate, special purpose subunit.
The entire power of the language can be leveraged to build up the patterns themselves or analyze and transform the programs that contain them.
Since SNOBOL's creation, newer languages such as Awk and Perl have made string manipulation by means of regular expressions fashionable.