Page 194 - DCAP310_INTRODUCTION_TO_ARTIFICIAL_INTELLIGENCE_AND_EXPERT_SYSTEMS

Introduction to Artificial Intelligence & Expert Systems

Notes
Example: The Mathematical function Compile can be used to make more efficient
versions of the code. In the following example, the details do not particularly matter; what
matters is that the sub expression {{com[_], Integer}} instructs Compile that expressions of the
form com[_] can be assumed to be integers for the purposes of compilation:
com[i_]:= Binomial[2i, i]
Compile[{x, {i, _Integer}}, x^com[i], {{com[_], Integer}}]

Pattern Matching and Strings

By far the most common form of pattern matching involves strings of characters. In many
programming languages, a particular syntax of strings is used to represent regular expressions,
which are patterns describing string characters. However, it is possible to perform some string
pattern matching within the same framework that has been discussed throughout this article.

Tree Patterns for Strings

Mathematically, strings are represented as trees of root String Expression and all the characters
in order as children of the root. Thus, to match “any amount of trailing characters”, a new
wildcard ___ is needed in contrast to _ that would match only a single character. In Haskell and
functional programming languages in general, strings are represented as functional lists of
characters. A functional list is defined as an empty list, or an element constructed on an existing
list. In Haskell syntax:
[] – an empty list
x:xs – an element x constructed on a list xs
The structure for a list with some elements is thus element:list. When pattern matching, we
assert that a certain piece of data is equal to a certain pattern. For example, in the function:
head (element:list) = element
We assert that the first element of head’s argument is called element, and the function returns
this.

Notes We know that this is the first element because of the way lists are defined, a single
element constructed onto a list. This single element must be the first. The empty list would
not match the pattern at all, as an empty list does not have a head (the first element that is
constructed).

In the example, we have no use for list, so we can disregard it, and thus write the function:
head (element:_) = element
The equivalent Mathematical transformation is expressed as
head[element, ]:=element

Example: It can be represented as,
StringExpression[“a”, ]
will match a string that has two characters and begins with “a”.

The same pattern in Haskell:
[‘a’, _]

188 LOVELY PROFESSIONAL UNIVERSITY