# How does the pattern matcher work?

how does it match this example?

f[3, h[4]] /. f[x_, z_[y_]] :> {x, y, z}


My guess is that the pattern matcher collects all the names in the expression f[3, h[4] ] in a list {f, 3, h, 4} and plugs them in (3 at a time) into the placeholders (the pattern variables) in the pattern f[x_, z_[y_]]?

It searches through all possibilities until it finds a match?

• {f, 4, 4} => f[f, 4[4] ] => False
• {3, f, f} => f[3, f[f] ] => False
• {3, f, 3} => f[3, f[3]] => False
• {3, f, h} => f[3, f[h]] => False
• {3, f, 4} => f[3, f[4]] => False
• {3, 3, f} => f[3, 3[f]] => False
• {3, 4, h} => f[3, 4[h]] => False

## - {3, h, 4} => f[3, h[4]] => True,

• {3, 3, 4},

• {3, h, f},
• {3, 4, f}

I am only guessing I would love to know how it really works?

• No. It compares part by part. Does the head match? You have f in both the target expression and the pattern, so yes. Good, next: does the first argument match? Yes, 3 matches _. Good, next: does the second argument match? That's h[4] and we have to test is against a compound pattern. So you start again with the head ... – Szabolcs Jun 26 '16 at 8:17
• You can read here en.wikipedia.org/wiki/Pattern_matching and also search for how a regular expression engine might be implemented. – Szabolcs Jun 26 '16 at 8:19
• Playing with ReplaceList may give you additional insight, as it returns a list of all matches in the order in which they are generated. – mikado Jun 26 '16 at 21:17
• The answer for this question might give you some idea about how to figure out how the pattern matching process works. – Wjx Jun 29 '16 at 3:10