# Orderless pattern matching of rule lists

I am looking for a compact way to specify a pattern to match a rule list with MatchQ that allows for enumerating the rules in the rule list in an arbitrary order. E.g. given:

ruleList1 = {"a" -> 10, "b" -> 2.2, "c" -> "str"}
ruleList2 = {"b" -> 2.2, "c" -> "str", "a" -> 10}


the following pattern will match both ruleList1 and ruleList2

MatchQ[ruleList,  {___, "a" -> _, ___, "b" -> _, ___} | {___, "b" -> _, ___, "a" -> _, ___}]


Can this pattern be written in a more compact form (e.g., by using OptionsPattern[])?

• What about sorting ruleList before trying pattern matching? In that case you should be able to use only the first comparison. As in MatchQ[Sort[ruleList2], {___, "a" -> _, ___, "b" -> _, ___}]. Having a "normal form" can simplify your work a lot. Commented Dec 3, 2013 at 16:03
• Related (perhaps duplicate): Patternmatching sets. Commented Dec 3, 2013 at 16:25

## OrderlessPatternSequence

MatchQ[#, {OrderlessPatternSequence[___,"a" -> _, ___, "b" -> _, ___]}] & /@
{ruleList1, ruleList2}


{True, True}

MatchQ[#, {OrderlessPatternSequence[___,"b" -> _, ___, "a" -> _, ___]}] & /@
{ruleList1, ruleList2}


{True, True}

Edit: see the bottom of this answer for my proposed solution.

Can you be sure your rule list is well formed, meaning that it is in fact a valid list of rules? I can think of a number of ways to approach this problem if that is the case. For example using Intersection:

{"a", "b"} === ruleList2[[All, 1]] ⋂ {"a", "b"}

True


Or using OptionValue:

2 == Length @ OptionValue[ruleList2, {"a", "b"}]

True


You could also sort the list Peltio suggested. This can be done somewhat automatically by using a head with the Orderless attribute:

SetAttributes[o, Orderless];

MatchQ[o @@ ruleList2, o["a" -> _, "b" -> _, ___]]

True


## Timings

Peltio questioned the efficiency of using Orderless and he was right to do so; on longer lists it is slower than the original method. Here are comparative timings performed in version 7. I left out the OptionValue method as it failed with errors; I need to look into that.

SetAttributes[timeAvg, HoldFirst]
timeAvg[func_] :=
Do[If[# > 0.3, Return[#/5^i]] & @@ Timing@Do[func, {5^i}], {i, 0, 15}]

rules = Rule @@@ RandomInteger[1000, {500, 2}];

{a, b} = {277, 514};

MatchQ[rules, {___, a -> _, ___, b -> _, ___} | {___, b -> _, ___, a -> _, ___}] // timeAvg
MatchQ[Sort@rules, {___, a -> _, ___, b -> _, ___}] // timeAvg
MatchQ[o @@ rules, o[a -> _, b -> _, ___]]          // timeAvg
{a, b} === rules[[All, 1]] ⋂ {a, b}                 // timeAvg

0.262

0.131

0.702

0.000093888


So on this sample pre-sorting cuts the time in half, whereas using Orderless nearly triples it. Intersection however is more than three orders of magnitude faster than any of the others.

Even better and more robust (in the case that the list contains expressions other than rules) appears to be using FilterRules before Intersection:

{a, b} === {a, b} ⋂ FilterRules[rules, {a, b}][[All, 1]] // timeAvg

0.000028928


## Proposed solution

Therefore, I propose using this:

ruleMatch[rules_List, keys_List] :=
Union @ keys === keys ⋂ FilterRules[rules, keys][[All, 1]]


Example:

ruleMatch[#, {"a", "b"}] & /@ {ruleList1, ruleList2}

{True, True}

• I beat you to your second answer by a second. Ironically, my first answer was nearly identical to your second one, I just decided to not include it now, which is what saved me that second. +1. Commented Dec 3, 2013 at 16:32
• @Leonid If I hadn't taken the time to copy the Intersection symbol... :^) Commented Dec 3, 2013 at 16:33
• Yeah, that's life :) Commented Dec 3, 2013 at 16:34
• @Mr.Wizard You mean, "If I hadn't been so obsessed with terse code..." :D
– rm -rf
Commented Dec 3, 2013 at 16:40
• @rm-rf That ain't nevah gonna change!! Commented Dec 3, 2013 at 16:43

One way would be to explicitly wrap both a list and a pattern in an Orderless container:

ClearAll[cont];
SetAttributes[cont, Orderless];
MatchQ[cont @@ ruleList1, cont["a" -> _, "b" -> _, ___]]

(* True *)

• Well crud, beaten by six seconds! Commented Dec 3, 2013 at 16:31