Page 193 - DCAP310_INTRODUCTION_TO_ARTIFICIAL_INTELLIGENCE_AND_EXPERT_SYSTEMS

Unit 10: Matching Techniques

Pattern Matching in Mathematica Notes

In Mathematica, the only structure that exists is the tree, which is populated by symbols. In the
Haskell syntax used thus far, this could be defined as:
data SymbolTree = Symbol String [SymbolTree]
An example tree could then look like
Symbol “a” [Symbol “b” [], Symbol “c” [] ]
In the traditional, more suitable syntax, the symbols are written as they are and the levels of the
tree are represented using [], so that for instance a[b,c] is a tree with a as the parent, and b and
c as the children.
A pattern in Mathematica involves putting “_” at positions in that tree. For instance, the pattern
A[_]
will match elements such as A[1], A[2], or more generally A[x] where x is any entity. In this case,
A is the concrete element, while _ denotes the piece of tree that can be varied. A symbol prepended
to _ binds the match to that variable name while a symbol appended to _ restricts the matches to
nodes of that symbol.

The Mathematica function Cases filters elements of the first argument that match the pattern in
the second argument:
Cases[{a[1], b[1], a[2], b[2]}, a[_] ]
evaluates to
{a[1], a[2]}

Pattern matching applies to the structure of expressions. In the example below,
Cases[ {a[b], a[b, c], a[b[c], d], a[b[c], de, a[b[c], d, e]}, a[b[_],
_] ]
returns
{a[b[c],d], a[b[c],de}
because only these elements will match the pattern a[b[_],_] above.
In Mathematical, it is also possible to extract structures as they are created in the course of
computation, regardless of how or where they appear. The function Trace can be used to
monitor a computation, and return the elements that arise which match a pattern. For example,
we can define the Fibonacci sequence as
fib[0|1]:=1
fib[n_]:= fib[n-1] + fib[n-2]
Then, we can ask the question: Given fib[3], what is the sequence of recursive Fibonacci calls?
Trace[fib[3], fib[[_]] returns a structure that represents the occurrences of the pattern
fib[_] in the computational structure:
{fib[3],{fib[2],{fib[1]},{fib[0]}},{fib[1]}}

Declarative Programming

In symbolic programming languages, it is easy to have patterns as arguments to functions or as
elements of data structures. 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.

LOVELY PROFESSIONAL UNIVERSITY 187