| 41 | More about Patterns |
Within the Wolfram Language, there’s a whole sublanguage of patterns. We’ve already seen some of its important elements.
_ ("blank") stands for anything. x_ ("x blank") stands for anything, but calls it x. _h stands for anything with head h. And x_h stands for anything with head h, and calls it x.
Define a function whose argument is an integer named n:
| In[1]:= | 
|
The function evaluates whenever the argument is an integer:
| In[2]:= | 
|
| Out[2]= | 
|
Sometimes you may want to put a condition on a pattern. You can do this with /; (“slash semi”). n_Integer/;n>0 means any integer that is greater than 0.
Give a definition which only applies when n>0:
| In[3]:= | 
|
The definition doesn’t apply to negative numbers:
| In[4]:= | 
|
| Out[4]= | 
|
The /; can go anywhere—even at the end of the whole definition.
Define different cases of the check function:
| In[5]:= | 
|
| In[6]:= | 
|
Some examples of the check function:
| In[7]:= | 
|
| Out[7]= | 
|
__ (“double blank”) stands for any sequence of one or more arguments. ___ (“triple blank”) stands for zero or more.
Define a function that looks for black and white (in that order) in a list.
The pattern matches black followed by white, with any elements before, between and after them:
| In[8]:= | 
|
| In[9]:= | 
|
| Out[9]= | 
|
By default, __ and ___ pick the shortest matches that work. You can use Longest to make them pick the longest instead.
Specify that the sequence between black and white should be as long as possible:
| In[10]:= | 
|
Now m grabs elements all the way to the last white:
| In[11]:= | 
|
| Out[11]= | 
|
bwcut effectively cuts out the longest run containing only black and white:
| In[12]:= | 
|
| In[13]:= | 
|
| Out[13]= | 
|
The pattern x_ is actually short for x:_, which means “match anything (i.e. _) and name the result x”. You can use notations like x: for more complicated patterns too.
Set up a pattern named m that matches a list of two pairs:
| In[14]:= | 
|
| In[15]:= | 
|
| Out[15]= | 
|
Name the sequence of black and white, so it can be used in the result:
| In[16]:= | 
|
| In[17]:= | 
|
| Out[17]= | 
|
As a final example, let’s use patterns to implement the classic computer science algorithm of sorting a list by repeatedly swapping pairs of successive elements that are found to be out of order. It’s easy to write each step in the algorithm as a replacement for a pattern.
Replace the first elements one finds out of order by ones that are in order:
| In[18]:= | 
|
| Out[18]= | 
|
| In[19]:= | 
|
| Out[19]= | 
|
At the beginning, we won’t know how long it’ll take to finish sorting a particular list. So the best thing is to use FixedPointList, which is like NestList, except that you don’t have to tell it a specific number of steps, and instead it just goes on until the result reaches a fixed point, where nothing more is changing.
| In[20]:= | 
|
| Out[20]= | 
|
| In[21]:= | 
|
| Out[21]= | 
|
ListLinePlot plots each list in a different color, showing how the sorting process proceeds:
| In[22]:= | 
|
| Out[22]= | 
|
Here’s the result for sorting a random length-20 list:
| In[23]:= | 
|
| Out[23]= | 
|
| patt/;cond | a pattern that matches if a condition is met | |
| ___ | a pattern for any sequence of zero or more elements (“triple blank”) | |
| patt.. | a pattern for one or more repeats of patt | |
| Longest[patt] | a pattern that picks out the longest sequence that matches | |
| FixedPointList[f,x] | keep nesting f until the result no longer changes |
41.1Find the list of digits for squares of numbers less than 100 that contain successive repeated digits. »
41.2In the first 100 Roman numerals, find those containing L, I and X in that order. »
No expected output
Many possible solutions of the form _:=_ or _=_
41.4Get a list of pairs of successive words in the Wikipedia article on alliteration that have identical first letters. »
41.5Use Grid to show the sorting process in this section for {4, 5, 1, 3, 2}, with successive steps going down the page. »
41.6Use ArrayPlot to show the sorting process in this section for a list of length 50, with successive steps going across the page. »
41.7Start with 1.0, then repeatedly apply the “Newton’s method” function (#+2/# )/2& until the result no longer changes. »
41.8Implement Euclid’s algorithm for GCD in which {a, b} is repeatedly replaced by {b, Mod[a, b]} until b is 0, and apply the algorithm to 12345, 54321. »
41.9Define combinators using the rules s[x_][y_][z_]x[z][y[z]], k[x_][y_]x, then generate a list by starting with s[s][k][s[s[s]][s]][s] and applying these rules until nothing changes. »
41.11Start from {1, 0} then for 200 steps repeatedly remove the first 2 elements, and append {0, 1} if the first element is 1 and {1, 0, 0} if it is 0 and get a list of the lengths of the sequences produced (tag system). »
41.12Start from {0, 0} then for 200 steps repeatedly remove the first 2 elements, and append {2, 1} if the first element is 0, {0} if the first element is 1, and {0, 2, 1, 2} if it is 2, and make a line plot of the lengths of the sequences produced (tag system). »
What are other pattern constructs in the Wolfram Language?
Except[patt] matches anything except patt. PatternSequence[patt] matches a sequence of arguments in a function. OrderlessPatternSequence[patt] matches them in any order. f[x_:v] defines v as a default value, so f[ ] is matched, with x being v.
How can one see all the ways a pattern could match a particular expression?
What does FixedPointList do if there’s no fixed point?
It’ll eventually stop. There’s an option that tells it how far to go. FixedPointList[f, x, n] stops after at most n steps.
- In a repeating pattern patt.., don’t forget to leave a space in e.g. 0 .. to avoid confusion with decimal numbers.
- Functions can have attributes that affect how pattern matching works. For example, Plus has attributes Flat and Orderless. Flat means that b+c can be pulled out of a+b+c+d. Orderless means that elements can be reordered, so a+c can be pulled out. (Flat is like the mathematical property of associativity; Orderless like commutativity.)
- The algorithm for sorting shown is usually called bubble sort. For a list of length n, it’ll typically take about n^2 steps. The built-in Wolfram Language function Sort is much faster, and takes only a little over n steps.
