Orderless pattern matching of rule lists

Question

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[])?

Answer 1

OrderlessPatternSequence

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

{True, True}

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

{True, True}

Answer 2

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}

Answer 3

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 *)