# Best way to modify values in a list of rules?

Recently I had to solve a problem similar to this:

Let's say I have a list of list of rules

Clear[a, b, c, d]
l = {{a -> 2, b -> 1, c -> 3, d -> 2}, {d -> 2, b -> 1, a -> 1, c -> 2},
{c -> 3, a -> 1, b -> 2}};


What is the best way to sort the values of {a, b, c} in each sublist without touching the rest of the sublist. So the first sublist should be:

{a -> 1, b -> 2, c -> 3, d -> 2}


and the whole result should be

{{a -> 1, b -> 2, c -> 3, d -> 2}, {d -> 2, b -> 1, a -> 1, c -> 2},
{c -> 3, a -> 1, b -> 2}}


There are no duplicates in the subsists (so a -> _ appears only once). The order of rules in the sublist does not matter.

In an effort to expand my pattern matching skills I would like to know: What's the best way to achieve this? Here "best" means elegant code, but still efficient enough to work ~10^5 subsists.

testdata =
Rule, {RandomSample[{a, b, c, d, e, f, g, h, i, j, k}, 10],
RandomReal[{-1, 1}, 10]}], {ii, 10^5}];


I'm posting my answer below, so that I won't get accused of not showing any effort:)

I cannot think of a better approach than your own method therefore I shall recast it in a generalized fashion.

With[{T = Thread},
normRls[l_, pat_] := l /. T[T[pat -> _] -> T[pat -> Sort[pat /. l]]]
]

normRls[#, {a, b, c}] & /@ testdata // Timing // First

1.31


This is however a bit slower than your hard-coded method:

normalize /@ testdata // Timing // First

1.045


Okay, let's try a little meta-programming:

genRule[x_, {y_}] := (x -> _) :> (x -> Slot[y])

genNorm[pat_List] :=
With[{body = MapIndexed[genRule, pat]},
# /. (body &) @@ Sort[pat /. #] &
]

genNorm[{a, b, c}] /@ testdata // Timing // First

0.889


Ah, that's more like it!

### Explanation

A request for explanation of the code was made. The first method is fairly straightforward after understanding the behavior of Thread:

Thread[{a, b, c} -> {1, 2, 3}]

{a -> 1, b -> 2, c -> 3}

Thread[{a, b, c} -> nonlist]

{a -> nonlist, b -> nonlist, c -> nonlist}


This is used three separate times, to generate e.g.: {a -> _, b -> _, c -> _}
then {a -> 1, b -> 2, c -> 3}, and then to combine them into:
{(a -> _) -> a -> 1, (b -> _) -> b -> 2, (c -> _) -> c -> 3}.

The "meta-programming" method is a bit more involved.

First let's look at the result, then how we get there:

genNorm[{q, r, s}]

#1 /. ({(q -> _) :> q -> #1,
(r -> _) :> r -> #2,
(s -> _) :> s -> #3} &) @@ Sort[{q, r, s} /. #1] &


We see that the output is a Function (&). This function takes a single argument, the (sub)list of rules to be modified. Upon it a replacement will eventually be done (#1 /. ...). The rules for that replacement are constructed by an internal Function:

({(q -> _) :> q -> #1,
(r -> _) :> r -> #2,
(s -> _) :> s -> #3} &)


the parameters (#1, #2, #3) of which are filled by applying (@@) to Sort[{q, r, s} /. #1] wherein #1 is the original (sub)list of rules. Sort[{q, r, s} /. #1] itself is hopefully self-explanatory. This internal function pulls the needed parts from the sorted list. For example, with the input:

{q -> 21, r -> 11, s -> 31, t -> 21}


The output is:

{(q -> _) :> q -> 11,
(r -> _) :> r -> 21,
(s -> _) :> s -> 31}


Which when applied yields:

{q -> 11, r -> 21, s -> 31, t -> 21}


Okay, so how is that function constructed?

The auxiliary function genRule is MapIndexed over the pattern list:

MapIndexed[genRule, {a, b, c}]

{(a -> _) :> a -> #1,
(b -> _) :> b -> #2,
(c -> _) :> c -> #3}


This expression is then named body (using With) and injected into: # /. (body &) @ Sort[pat /. #] & which you should recognize as the (nested) function detailed above.

• Thank you for the answer (+1). Some wonderful ideas. But, I think this answer would be much better if you could ad a line or two explaining what the code does (for those who don't have MMA at hand or are not so proficient -- actually I'm still deciphering the meta-programming trick:). – Ajasja Feb 14 '13 at 21:43
• @Ajasja Done. Please tell me if my explanation is satisfactory. I never know what to include and what to leave out I'm afraid. – Mr.Wizard Feb 14 '13 at 22:07
• @Ajasja I realize that this can be made faster by using genNorm[pat_List] := With[{body = MapIndexed[genRule, pat]}, Replace[#, body & @@ Sort[pat /. #], {1}] &] -- that is replace at level one. – Mr.Wizard Feb 20 '13 at 21:12

Here is my solution: I first retrieve the values, sort them and then use rule replacement to apply the changes.

Clear@normalize
normalize[l_] := Block[{av, bv, cv},
(*Get sorted values*)
{av, bv, cv} = Sort[{a, b, c} /. l];
(*Modify the original lis*)
l /. {Rule[a, _] -> Rule[a, av],
Rule[b, _] -> Rule[b, bv],
Rule[c, _] -> Rule[c, cv]}
]

normalize /@ l
(* out =>
{{a -> 1, b -> 2, c -> 3, d -> 2}, {d -> 2, b -> 1, a -> 1,
c -> 2}, {c -> 3, a -> 1, b -> 2}}
*)


This takes about 2 seconds on my computer

AbsoluteTiming[result = normalize /@ testdata;]
(*=> {2.319133, Null}*)


Here is an alternative:

Clear@sortKeys
sortKeys[list_, keys_] := Module[{keysInList, values, rules},
{keysInList, values} = (rules = FilterRules[#, keys]) /. Rule -> List // Transpose;
] & /@ list


This first filters the rules in a sublist corresponding to the input keys ({a, b, c}) we wish to sort by and then keeps a separate list of keys that actually appear in the sublist (keysInList) and their values (this is to handle missing keys). Then it sorts the values and replaces a -> original value with a -> sorted value (the MapThread is used to construct a rule list).

Usage:

sortKeys[l, {a, b, c}]
(* {{a -> 1, b -> 2, c -> 3, d -> 2}, {d -> 2, b -> 1, a -> 1, c -> 2},
{c -> 3, a -> 1, b -> 2}} *)


This can be simplified if it can be guaranteed that all the sublists will have all the keys.

• Thanks for the answer. I think a short sentence explaining what the code does would make this a much better answer. – Ajasja Feb 14 '13 at 10:19
• @Ajasja Explanation added :) – rm -rf Feb 14 '13 at 14:54
• Thanks +1. Why is RuleDelayed needed? (Instead of a normal Rule) – Ajasja Feb 14 '13 at 15:06
• Probably not needed in this case, but I do it out of habit, when the RHS is a named pattern (or more generally, when it's not something of the form HeadA -> HeadB or SymbolA -> SymbolB) – rm -rf Feb 14 '13 at 16:11

In a comment elsewhere, @Mr.Wizard suggested that associations might be useful for this question. Here is my attempt:

normalizeAssoc[keys_][l_] :=
<| l, AssociationThread[keys -> Sort @ Lookup[l, keys, 0]] |>


... and here it is in action:

Take[testdata, 2]

(* {{h->0.074356,i->0.756409,f->0.456624,b->-0.0342208,c->0.634687,
d->0.0939196,e->-0.527057,g->-0.62371,k->-0.41238,a->0.0599702},
{a->-0.665407,g->0.414135,i->-0.909054,e->-0.727194,c->-0.872878,
b->-0.125237,j->0.829395,k->-0.416614,h->-0.819966,f->0.815137}} *)

normalizeAssoc[{a, b, c}] /@ Take[testdata, 2]

(* {<|h->0.074356,i->0.756409,f->0.456624,b->0.0599702,c->0.634687,
d->0.0939196,e->-0.527057,g->-0.62371,k->-0.41238,a->-0.0342208|>,
<|a->-0.872878,g->0.414135,i->-0.909054,e->-0.727194,c->-0.125237,
b->-0.665407,j->0.829395,k->-0.416614,h->-0.819966,f->0.815137|>} *)


This function operates equally well when the original rules are in list form or in associations.

The question's construction of testdata will generate some sublists in which a, b, or c is missing. The problem statement is silent on how to handle such cases, so I have arbitrarily decided to treat the values of missing keys as zero. If a different value is appropriate, simply adjust the expression Lookup[..., 0]. It is left as an exercise for the reader if some other strategy is required.

Note that the result contains associations instead of sublists. If this is unacceptable, then we can use:

normalizeAssoc2[keys_][l_] :=
normalizeAssoc[keys][l] // Normal


Naturally, this takes a little longer to run. Speaking of run time, here are some timings on my machine:

    normalizeAssoc               : 1.39s
normalizeAssoc2              : 2.07s

normalize (from Ajasja)      : 5.92s
normRls   (#1 from Mr.Wizard): 4.26s
genNorm   (#2 from Mr.Wizard): 3.56s


Like all microbenchmarks, these timings should be taken with a grain of salt. I found that the running times of all functions changed radically as new random variations of testdata were generated, presumably due to the randomized key order. However, repeated runs showed that the relative performance of the functions remained reasonably consistent.

• Thank you. That is cleaner than what I had. – Mr.Wizard Feb 14 '15 at 10:50

edit: this is actually not doing what you want, i sorted the order of the rules without changing the rules.

rulelist = {a -> 1, b -> 2, cc -> 4, c -> -1};
sortpos = Position[ rulelist ,  r_Rule /; MemberQ[{a, b, c}, r[]]];
sorted = Sort[
Take[rulelist, #][] & /@ (sortpos) , #1[] < #2[] &];
(rulelist[[sortpos[[#]]]] = sorted[[#]]) & /@ Range[Length[sortpos]];
rulelist

{c -> -1, a -> 1, cc -> 4, b -> 2}


Take 2, I think this is what you want, changine the rules so that a-> min value, etc and reordering the rules.. I think it does basically what you did, except I didnt "hard code" the a,b,c into the algotithm. If performace suffers a tad that might be a fair trade.

rulelist = {a -> 1, b -> 2, cc -> 4, c -> -1};
desiredorder = {a, b, c};
values = Sort[ desiredorder /. rulelist];
rulelist = rulelist /. (x_ -> y_) /;
MemberQ[desiredorder, x] :> (x ->values[[First[Position[desiredorder, x]][]]]);
sortpos =
Position[ rulelist ,  r_Rule /; MemberQ[desiredorder, r[]]];
(rulelist[[sortpos[[#]]]] = desiredorder[[#]] -> values[[#]]) & /@
Range[Length[desiredorder]];

rulelist -> {a -> -1, b -> 1, cc -> 4, c -> 2}


(If you dont care about the order of the rules, drop the last two lines)

• Thanks for the answer. I think a short sentence explaining what the code does would make this a much better answer. – Ajasja Feb 14 '13 at 10:20