We now provide a more general motivation for the pattern matcher, and give a complete account of its operation.
If we wish to search down a list for an item we can use a test something like
item = hd(list)to accomplish this. But list representations of more complex situations do not exhibit their significant features in terms of single items considered in isolation. Rather the norm is one of a context or co-occurrence of elements. Thus we are much more likely to want to know whether a list contains two designated elements occurring in a particular order, or even whether it satisfies some rather more complex condition. E.g. does the sentence start with a noun phrase? For now we consider only the relatively simple cases.
Supposing we have this list
[a b c d e] -> x;In some problem we might wish to test might be to establish whether it contains "b" and "d" occurring in that order. Now
member("b",x) =>
** <true>
member("d", x) =>
**<true>
tell us that both are present i.e.
member("b", x) and member("d",x) =>
** <true>
but we know nothing of their relative positions in x nor indeed of
their intervening or surrounding context.
We can capture this ordering of "b" and "d" for example:
x(1) == "b" and x(2) == "d"which specifies that "d" should immediately follow "b: in the list. In fact the relationship that does obtain in X has the form
x(2) == "b" and x(4) == "d"In this way we can specify any arbitrary patterning of elements in a list structure. It will however be very tedious to try all possible combination of pairs of successive numbers. The situation gets even worse if you merely want to test whether "d" occurs SOMEWHERE to the right of "b", although you do not mind where exactly.
This need to be able to give a more complex specification of the structure of a list is met by the procedure MATCHES that tests a given list for the presence of some specified pattern.