Wolfram Computation Meets Knowledge

41 More about Patterns

41More 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:
digitback[n_Integer] := Framed[Reverse[IntegerDigits[n]]]
The function evaluates whenever the argument is an integer:
{digitback[1234], digitback[6712], digitback[x], digitback[{4, 3, 2}], digitback[2^32]}
 
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:
pdigitback[n_Integer /; n > 0] := Framed[Reverse[IntegerDigits[n]]]
The definition doesn’t apply to negative numbers:
{pdigitback[1234], pdigitback[-1234], pdigitback[x], pdigitback[2^40]}
 
The /; can go anywhereeven at the end of the whole definition.
Define different cases of the check function:
check[x_, y_] := Red /; x > y
check[x_, y_] := Green /; x <= y
Some examples of the check function:
{check[1, 2], check[2, 1], check[3, 4], check[50, 60], check[60, 50]}
 
__ (“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:
blackwhite[{___, Black, m___, White, ___}] := {1, m, 2, m, 3, m, 4}
blackwhite[{RGBColor[1, 0.5, 0.5], GrayLevel[0], RGBColor[1, 0.5, 0], RGBColor[1, 1, 0], RGBColor[1, 1, 0], GrayLevel[1], RGBColor[ 0.5, 0, 0.5], GrayLevel[1]}]
 
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:
blackwhitex[{___, Black, Longest[m___], White, ___}] := {1, m, 2, m, 3, m, 4}
Now m grabs elements all the way to the last white:
blackwhitex[{RGBColor[1, 0.5, 0.5], GrayLevel[0], RGBColor[1, 0.5, 0], RGBColor[1, 1, 0], RGBColor[1, 1, 0], GrayLevel[1], RGBColor[ 0.5, 0, 0.5], GrayLevel[1]}]
 
x|y|z matches x, y or z. x.. matches any number of repetitions of x.
bwcut effectively cuts out the longest run containing only black and white:
bwcut[{a___, Longest[(Black | White) ..], b___}] := {{a}, Red, {b}}
bwcut[{RGBColor[1, 0.5, 0.5], RGBColor[1, 0.5, 0.5], GrayLevel[0], GrayLevel[1], GrayLevel[1], GrayLevel[0], GrayLevel[0], RGBColor[ 1, 1, 0]}]
 
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:
grid22[m : {{_, _}, {_, _}}] := Grid[m, Frame -> All]
{grid22[{{a, b}, {c, d}}], grid22[{{12, 34}, {56, 78}}], grid22[{123, 456}], grid22[{{1, 2, 3}, {4, 5, 6}}]}
 
Name the sequence of black and white, so it can be used in the result:
bwcut[{a___, r : Longest[(Black | White) ..], b___}] := {{a}, Framed[Length[{r}]], {b}}
bwcut[{RGBColor[1, 0.5, 0.5], RGBColor[1, 0.5, 0.5], GrayLevel[0], GrayLevel[1], GrayLevel[1], GrayLevel[0], GrayLevel[0], RGBColor[ 1, 1, 0]}]
 
{5, 4, 1, 3, 2} /. {x___, b_, a_, y___} /; b > a -> {x, a, b, y}
 
Do the same operation 10 times, eventually sorting the list completely:
NestList[(# /. {x___, b_, a_, y___} /; b > a -> {x, a, b, y}) &, {4, 5, 1, 3, 2}, 10]
 
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.
Do the operation until a fixed point is reached:
FixedPointList[(# /. {x___, b_, a_, y___} /; b > a -> {x, a, b, y}) &, {4, 5, 1, 3, 2}]
 
Transpose to find the list of elements appearing first, second, etc. at successive steps:
Transpose[%]
 
ListLinePlot plots each list in a different color, showing how the sorting process proceeds:
ListLinePlot[%]
 
Here’s the result for sorting a random length-20 list:
ListLinePlot[ Transpose[ FixedPointList[(# /. {x___, b_, a_, y___} /; b > a -> {x, a, b, y}) &, RandomSample[Range[20]]]]]
 
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. »
Expected output:
Out[]=
41.2In the first 100 Roman numerals, find those containing L, I and X in that order. »
Expected output:
Out[]=
41.3Define a function f that tests whether a list of integers is the same as its reverse. »
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. »
Sample expected output:
Out[]=
41.5Use Grid to show the sorting process in this section for {4, 5, 1, 3, 2}, with successive steps going down the page. »
Expected output:
Out[]=
41.6Use ArrayPlot to show the sorting process in this section for a list of length 50, with successive steps going across the page. »
Sample expected output:
Out[]=
41.7Start with 1.0, then repeatedly apply the “Newtons method” function (#+2/# )/2& until the result no longer changes. »
Expected output:
Out[]=
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»
Expected output:
Out[]=
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. »
Expected output:
Out[]=
41.10Remove all trailing 0’s from the digit list for 100!»
Expected output:
Out[]=
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). »
Expected output:
Out[]=
Expected output:
Out[]=
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?
Use ReplaceList. Replace gives the first match; ReplaceList gives a list of all of them.
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.
Next Section