The B, D example is of course but one of an infinite variety of patternings that we might want to look for. So our specification of a pattern has to be couched in a suitably descriptive language. The pattern for `B immediately followed by D' would be:
[== b d ==]But the `B followed somewhere by D' pattern would be specified like this:
[== b == d ==]Where `==' denotes any number of list elements (including no elements). Thus all of these lists should meet that specification:
[a b c d e]
[b d]
[b a a c d f]
To test a given list, say X, for presence of this specified pattern
we'd call MATCHES like this
x matches [== b == d ==] =>
** <true>
What result would you expect from the following:
x matches [a == e] =>
x matches [a == d == e] =>
The pattern specification we've adopted clearly admits of a lot of
variation in x - it's a rather sloppy fit: and often that is a useful
way of representing generality.
There are a number of ways in which we can tighten it up, when required. We might for example want just one intervening element between B and D:
x matches [== b = d ==] =>
** <true>
These two symbols == and = are basic descriptors of pattern shape
and we may think of them as `Gobbling up' intervening list items. We
can call `=' Gobble-one and `==' Gobble-any. (These names were suggested
by the late Max Clowes.)
Gobble-one and Gobble-any help us characterise the linear shape of a pattern. We may also want to characterise its structural organisation. For example that the first element in the target list must itself be a list - as it is in CUPBOARD for example.
cupboard matches [[==] blanket ==] =>
** true
And this device may of course be used to dig arbitrarily `deep' into
a list structure.
The pattern is then a sort of picture with lots of missing details, of the kind of list we are looking for.