# Orderless breaks pattern match

Bug introduced in 10.3 or earlier and persisting through 12.0.0
10.0.2 is not affected.

I am perplexed by the effect of Orderless on pattern matching. Starting from a clean Kernel (i.e. after using Quit), I find the following expected match for function g without any definitions or attributes

MatchQ[g[a[1], b[1]], g[(Y : (a | b))[i__], b[1]]]
(* True *)


If I do the same for a symbol f with Attributes[f] = {Orderless}

Attributes[f] = {Orderless};
MatchQ[f[a[1], b[1]], f[(Y : (a | b))[i__], b[1]]]
(* False *)


it returns False. I would have expected True. If I replace i__ with 1 on the RHS I get True again.

MatchQ[f[a[1], b[1]], f[(Y : (a | b))[1], b[1]]]
(* True *)


The same goes for

MatchQ[f[a[1], b[1]], f[(Y : (a | c))[i__]]


So the issue does not seem to be that b somehow gets matched on the wrong side. Also Orderless seems to prefer the same (flipped) order regardless of whether I change i__ to 1. (And this should be irrelevant anyway since f has orderless.

What am I missing here?

• Orderless sorts the symbols. Have a look at OrderlessPatternSequence. E.g., MatchQ[f[a[1], b[1]], f[OrderlessPatternSequence[(Y : (a | b))[i__], b[1]]]] might do what you want. – Henrik Schumacher Mar 21 '19 at 11:20
• @HenrikSchumacher, thanks. I seem to have been completely mistaken about what Orderless does then. I understand it would sort the result, but for pattern matching it should try all orders again right? So making the order unimportant. "In matching patterns with Orderless functions, all possible orders of arguments are tried." Now it seems that each time I use a pattern on a orderless symbol I will need to use OrderlessPatternSequence myself. How should I understand the documentation if it does not really mean that all orders will be tried for pattern matching. – Kvothe Mar 21 '19 at 11:33
• "How should I understand the documentation...?" Well, that's a question for which I don't have any answer. Maybe I am also mistaken, things should work as you expected, and there is some other issue that I don't see at the moment. Let's wait for further opinion. – Henrik Schumacher Mar 21 '19 at 11:38
• Reported as a bug. – Daniel Lichtblau Mar 21 '19 at 15:27
• @march As best I can tell they are different issues. – Daniel Lichtblau Mar 21 '19 at 18:18