Take the 2-minute tour ×
Mathematica Stack Exchange is a question and answer site for users of Mathematica. It's 100% free, no registration required.

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

share|improve this question
3  
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. –  Peltio Dec 3 '13 at 16:03
1  
Related (perhaps duplicate): Patternmatching sets. –  István Zachar Dec 3 '13 at 16:25
add comment

2 Answers

up vote 7 down vote accepted

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}
share|improve this answer
    
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. –  Leonid Shifrin Dec 3 '13 at 16:32
    
@Leonid If I hadn't taken the time to copy the Intersection symbol... :^) –  Mr.Wizard Dec 3 '13 at 16:33
    
Yeah, that's life :) –  Leonid Shifrin Dec 3 '13 at 16:34
1  
@Mr.Wizard You mean, "If I hadn't been so obsessed with terse code..." :D –  rm -rf Dec 3 '13 at 16:40
    
@rm-rf That ain't nevah gonna change!! –  Mr.Wizard Dec 3 '13 at 16:43
show 3 more comments

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 *)
share|improve this answer
2  
Well crud, beaten by six seconds! –  Mr.Wizard Dec 3 '13 at 16:31
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.