Sorting a list of rules

Question

When we give several definitions for a function f, the DownValues of f are automatically sorted with respect to the domain defined by the pattern:

f[x_]:=2;
f[x_?Positive] := 3;
f[1]=4;
DownValues[f]

(* {HoldPattern[f[1]]:>4,HoldPattern[f[x_?Positive]]:>3,HoldPattern[f[x_]]:>2} *)

I am wondering if it possible to sort a list of rules in the same way. For example,

{_->6, _?Positive->3, 1->4}

should be sorted as

{1->4, _?Positive->3, _->6}

Of course it can be done by transforming the list of rules to a list of function definitions, and then translate back the (automatically sorted) DownValues of that function to the original rules. I am looking for a way not using DownValues. Therefore, an alternative title of this question could be: how does Mathematica sort DownValues?

Answer 1

When using the function ReplaceAll, the result may depend on the order in which the rules are given. This is due to the fact that when more than one rule can be applied, ReplaceAll uses the first rule in the list. Here is an example:

rules={_Integer->1,_?EvenQ->2,1->4, 2->5, _?OddQ->3}
(* {_Integer->1,_?EvenQ->2,1->4,2->5,_?OddQ->3} *)

Range[10] /. rules
(* {1,1,1,1,1,1,1,1,1,1} *)

Range[10] /. Reverse[rules]
(* {3,5,3,2,3,2,3,2,3,2} *)

I want to use the rules in such a way that the most specific rule is used first. We know that the DownValues of a function are automatically sorted such that the most specific definition is used first. We call this mechanism in the following sorting function for rules:

sortrules[rules_] := Module[{f}, (f[#[[1]]]=#[[2]])& /@ rules; DownValues[f] /. f[x_]:>x]

sortrules[rules]
(* {HoldPattern[1]:>4,HoldPattern[2]:>5,HoldPattern[_Integer]:>1,
     HoldPattern[_?EvenQ]:>2,HoldPattern[_?OddQ]:>3} *)

This is good, but not perfect: it is not recognized that the last two rules are more specific than the third one. That can be improved by using the pattern _Integer instead of _ in the last two rules.

sortrules[{_Integer->1, _Integer?EvenQ->2, 1->4, 2->5, _Integer?OddQ->3}]
(* {HoldPattern[1]:>4, HoldPattern[2]:>5, HoldPattern[_Integer?EvenQ]:>2, 
    HoldPattern[_Integer?OddQ]:>3, HoldPattern[_Integer]:>1}

My problem is how we can arrive at more or less the same result by using other Mathematica functions than DownValues.

This link provided by @Shadowray refers to a very interesting discussion on how to order patterns with respect to the specificity. My question is very related to this discussion and I completely agree with @Mr.Wizard that it can be considered as a duplicate, though I am only looking for existing Mathematica functions, not creating new ones.

As mentioned by Shadowray, in the context GeneralUtilities` we find some functions for sorting patterns. The most promising is the function PatternSort, of which the documentation states that it returns a list of patterns, in order of most specific to least specific.

GeneralUtilities`PatternSort[rules[[All, 1]]]
(* {_?OddQ,2,1,_?EvenQ,_Integer} *)

Obviously, this result is not in agreement with the documentation: the most specific patterns 1 and 2 follow the less specific pattern _?OddQ.

By using Information on these functions, we find that at the end they call the function Internal`ComparePatterns. That function cannot handle patterns that contain a function test very well:

Internal`ComparePatterns[1,_?(True&)]
(* Incomparable *)

So my conclusion is that using DownValues for sorting patterns or rules with respect to specificity, as done above, has to be preferred over using the functions in the context GeneralUtilities`.