23
$\begingroup$

I have a function which has some general behavior, but that should act on some specific kinds of objects in some other way. I know that Mathematica is supposed to automatically order the rules so that the more specific rules are applied first. Nevertheless, I want to be sure that I can change the order manually in case Mathematica is not able to do this automatically in my case.

edit: A simple example of such a situation where rule reordering takes place is (taken out of Leonid Shifrin's book, which I highly recommend)

In[1]:= Clear[f];
In[2]:= f[x_]:= Sin[x];
In[3]:= f[x_?EvenQ]:= x;
In[4]:= f[x_?OddQ]:= x^2;
In[5]:= {f[1], f[2], f[3], f[4], f[3/2], f[Newton]} 
Out[1]:= {1, 2, 9, 4, Sin[3/2], Sin[Newton]} 

So the Sin definition takes place last even though it was defined first. So for example in this case is there a way to make the Sin always apply first without unsetting the other definitions? Or conversely to make sure a definition is used first even though it was declared last?

Thanks, Lior

$\endgroup$
  • 2
    $\begingroup$ Can we get a minimum example of the behavior you want to change? $\endgroup$ – Jason B. Feb 10 '16 at 11:29
  • 2
    $\begingroup$ The rules are given by DownValues[f]. Mathematica evaluates the rules in the order given there. You can change DownValues manually, e.g. DownValues[f] = { stuff } if you're not happy with how Mathematica ordered the rules automatically. $\endgroup$ – LLlAMnYP Feb 10 '16 at 13:20
  • $\begingroup$ I edited, adding Jason B's request. @LLlAMnYP is there a way to do this without knowing the existing definitions in advance? or maybe use Prepend? $\endgroup$ – Lior Blech Feb 10 '16 at 13:23
  • 1
    $\begingroup$ It seems there is no general answer: How is pattern specificity decided? $\endgroup$ – Kuba Feb 10 '16 at 13:30
  • $\begingroup$ Lior, I encourage you not to Accept an answer so quickly. People often pass over questions with Accepted answers as they appear to be resolved. I like to wait at least 24 hours to give everyone around the world a chance to see my question before Accepting an answer. However it is your prerogative and you can Accept or change your Accept at any time. $\endgroup$ – Mr.Wizard Feb 10 '16 at 14:58
21
$\begingroup$

General

The definitions get reordered at definition-time by a part of the pattern matcher, that takes care of automatic rule reordering. It does so, based on relative generality of rules, as far as it is able to determine that. This is not always possible, so when it can't determine which of the two rules is more general, it appends the rules to DownValues (or SubValues, UpValues, etc.) in the order the definitions are given. This is described in the documentation. Some past discussions on this site, containing more information about that, can be found here and here.

Manipualations with DownValues

As mentioned in comments and the other answer, one general way to change the order of definitions is to manipulate DownValues directly, assigning to DownValues[f] the rules in the order you want. This technique has been described in the documentation, and also extensively in David Wagner's book (which is available for free).

The most general way is indeed

DownValues[f] = {rules}

However, sometimes a more special form of rule rearrangement is handy: if you give a new definition, which you want to be tried first, but which you know for sure to be added last, you can do this:

f[...]:=your-new-definition;
DownValues[f] = RotateRight[DownValues[f]]

In which case, your definitions becomes the first, while all the other definitions maintain the same relative order as before. This trick has been discussed by Wagner in his book. Another example where this trick has been put to use, is here.

Using symbolic tags to fool the reordering system

This trick I haven't seen used by others, although I am sure I was not the only one to come up with it. Basically, you do something like this:

ClearAll[f, $tag];
f[x_] /; ($tag; True) := Sin[x];
f[x_?EvenQ] := x;
f[x_?OddQ] := x^2;

The pattern-matcher can no longer decide that the first rule is more general than the others, since it can't know what $tag is, until the code runs. In practice, $tag should have no value, and serves only to ensure that rules aren't reordered. It is also convenient since, if you no longer need such definition, you can simply do

DownValues[f] = DeleteCases[DownValues[f], def_/;!FreeQ[def, $tag]]

When it breaks

One other subtle point, that tends to be overlooked, is that definitions which don't contain patterns (underscores and other pattern-building blocks), are stored in a separate hash-table internally. In DownValues list, they always come first - since indeed, they are always more specific than those containing patterns. And no matter how you reorder DownValues, you can't bring those "down" the definitions list. For example:

 ClearAll[ff, $tag];
 ff[x_] /; ($tag; True) := Sin[x];
 ff[x_?EvenQ] := x;
 ff[x_?OddQ] := x^2;
 ff[0] = 0;
 ff[1] = 10;

Let's check now:

DownValues[ff]

(*

    {HoldPattern[ff[0]] :> 0, HoldPattern[ff[1]] :> 10, 
     HoldPattern[ff[x_] /; ($tag; True)] :> Sin[x], 
     HoldPattern[ff[x_?EvenQ]] :> x, HoldPattern[ff[x_?OddQ]] :> x^2}
*)

We can attempt to reorder manually:

 DownValues[ff] = DownValues[ff][[{3, 4, 5, 1, 2}]]

only to discover that this didn't work:

DownValues[ff]

(*

    {HoldPattern[ff[0]] :> 0, HoldPattern[ff[1]] :> 10, 
     HoldPattern[ff[x_] /; ($tag; True)] :> Sin[x], 
     HoldPattern[ff[x_?EvenQ]] :> x, HoldPattern[ff[x_?OddQ]] :> x^2}
*)

In some sense, this is good, because e.g. this makes standard memoization idiom f[x_]:=f[x]=... both possible and stable / robust. But this is something to keep in mind.

You can still make these definitions be the last by using the tag-trick:

ClearAll[ff, $tag, $tag1];
ff[x_] /; ($tag; True) := Sin[x];
ff[x_?EvenQ] := x;
ff[x_?OddQ] := x^2;
ff[0] /; ($tag1; True) = 0;
ff[1] /; ($tag1; True) = 10;

So that

ff[1]

(* Sin[1] *)

But then you considerably slow down the lookup for such definitions, even when they eventually fire.

$\endgroup$
  • 3
    $\begingroup$ We can attempt to reorder manually: DownValues[ff] = DownValues[ff][[{3, 4, 5, 1, 2}]] only to discover that this didn't work: very insightful, +1 $\endgroup$ – LLlAMnYP Feb 10 '16 at 15:11
21
$\begingroup$

Actually we have direct control over this via a System Option. Set:

SetSystemOptions["DefinitionsReordering" -> "None"];

Then:

Clear[f];
f[x_] := Sin[x];
f[x_?EvenQ] := x;
f[x_?OddQ] := x^2;
{f[1], f[2], f[3], f[4], f[3/2], f[Newton]}
{Sin[1], Sin[2], Sin[3], Sin[4], Sin[3/2], Sin[Newton]}

Restore the default behavior with:

SetSystemOptions["DefinitionsReordering" -> "Default"];

By the way this reordering takes significant time; by disabling it I was able to make an already efficient solution more than twice as fast for How to select minimal subsets?


Prophylactic

Leonid expressed concern about the generality of the effect of this setting. Here is an attempt to localize its behavior.

SetAttributes[nonOrder, {HoldFirst, SequenceHold}]

nonOrder[{body_}] :=
  Internal`WithLocalSettings[
    SetSystemOptions["DefinitionsReordering" -> "None"],
    body,
    SetSystemOptions["DefinitionsReordering" -> "Default"]
  ]

nonOrder[LHS_ = RHS_] := nonOrder[LHS, RHS]
nonOrder[LHS_, RHS_] := nonOrder @ {LHS = Unevaluated @ RHS}
nonOrder[sd : (LHS_ := RHS_)] := nonOrder @ {sd}

With this internal definitions made during the evaluation of the right hand side in Set are ordered normally.

ClearAll[f, foo, bar, baz]

foo[] := (bar[x_] := Sin[x]; bar[x_?OddQ] := x^2; baz)

nonOrder[  f[1] = foo[]  ];
nonOrder[  f[x_ /; x > 1] := 2 + 2  ]

?f
?bar
Global`f

f[1]=baz

f[x_/;x>1]:=2+2


Global`bar

bar[x_?OddQ]:=x^2

bar[x_]:=Sin[x]

Note that f is not automatically ordered, as intended, while bar is ordered, as intended.

$\endgroup$
  • $\begingroup$ Interesting. I forgot about this option, +1. Will still keep my answer, since it describes alternative techniques and gives some extra info. $\endgroup$ – Leonid Shifrin Feb 10 '16 at 15:05
  • $\begingroup$ Very nice, didn't know about this option. +1 $\endgroup$ – LLlAMnYP Feb 10 '16 at 15:08
  • $\begingroup$ @Leonid We're still writing complementary answers IMO. Mine is short but hopefully pithy, and yours is extensive and views the problem from multiple angles. I'll never match your Guru badge count but I think we make a good duo. $\endgroup$ – Mr.Wizard Feb 10 '16 at 15:08
  • $\begingroup$ Actually, using this option in practice is pretty scary, since it changes the ordering policy globally. So if some of the code that runs during the time when this stays changed, relies in automatic reordering, things can break in very subtle ways. And this doesn't even have to be one's own code, it could be in some of the functionality one is using (perhaps without even knowing about it). $\endgroup$ – Leonid Shifrin Feb 10 '16 at 15:10
  • 1
    $\begingroup$ @Algohi Good question. I'm glad someone is actually reading my code. :-) It is an attempt to make sets within nonOrder behave more like they do outside of nonOrder. One can write foo = Unevaluated[2 + 2]; and then Definition[foo] to see that we did manage to set "foo = 2 + 2" internally. The Unevaluated you mention is needed to allow nonOrder[bar = Unevaluated[2 + 2]]; to work the same. There are surely other edge cases I did not handle but that one came to mind so I included it. $\endgroup$ – Mr.Wizard Feb 11 '16 at 7:53
10
$\begingroup$

This is more of an extended comment in response to

@LLlAMnYP is there a way to do this without knowing the existing definitions in advance? or maybe use Prepend?

You can roll a function like so:

SetAttributes[makeDef, HoldAllComplete]
makeDef[f_Symbol, expr_, n_Integer] := 
 Module[{dVal}, 
  Block[{f}, Evaluate[expr]; dVal = First[DownValues[f]]]; 
  DownValues[f] = Insert[DownValues[f], dVal, n];]

Then

f[x_?EvenQ] := x;
f[x_?OddQ] := x^2;
DownValues[f]
{HoldPattern[f[x_?EvenQ]] :> x, HoldPattern[f[x_?OddQ]] :> x^2}
makeDef[f, f[x_] := Sin[x], 1]
DownValues[f]
{HoldPattern[f[x_]] :> Sin[x], 
 HoldPattern[f[x_?EvenQ]] :> x,
 HoldPattern[f[x_?OddQ]] :> x^2}

makeDef takes the symbol for which rules are being set as the first argument, the expression creating the rule as the second argument, and the position at which the rule will be inserted as the third argument.

$\endgroup$
  • $\begingroup$ @Kuba because when f is Blocked, there's only one DownValue made. Of course, I didn't generalize this to the cases where expr is a big long compound expression that creates several DownValues $\endgroup$ – LLlAMnYP Feb 10 '16 at 14:40
  • $\begingroup$ And of course, this also suppresses routines that check pattern specificity and all that, so you can end up with multiple entries of the form {f[x_] :> dVal1, f[x_] :> dVal2} and so on. But it's just a little example that shows how to have more control over the order of rules. $\endgroup$ – LLlAMnYP Feb 10 '16 at 14:43
  • $\begingroup$ Right, wasn't paying attention, sorry :) $\endgroup$ – Kuba Feb 10 '16 at 14:46
  • $\begingroup$ Wow great answer! I was writing my own (below) when you published this so I didn't see, but this is even better! $\endgroup$ – Lior Blech Feb 10 '16 at 14:50
  • $\begingroup$ @LiorBlech Yes, makeDef[f, expr, 1] is equivalent to your approach, but saves you the trouble of writing out HoldPattern[f[x_]] :> stuff and lets you use the usual syntax. $\endgroup$ – LLlAMnYP Feb 10 '16 at 14:52
7
$\begingroup$

Updated

Updated twice, once to force autoloading, and a second time to eliminate duplicate *Values

I will answer the last part of the question, specifically:

Or conversely to make sure a definition is used first even though it was declared last?

Here is a variant of @LLlAMnYP's approach. Instead of defining a new function to insert a DownValue in front of the others, I will use a wrapper to indicate to TagSetDelayed that a DownValue should be inserted in front (I owe this idea to @TaliesinBeynon):

Initial /: Verbatim[TagSetDelayed][Initial[sym_], lhs_, rhs_] := With[
    {
    new = Block[{sym},
        TagSetDelayed[sym, lhs, rhs];
        First@Language`ExtendedDefinition[sym]
    ],
    protect=Unprotect[sym]
    },

    (* Force autoloading of sym *)
    sym;
    Quiet@MakeBoxes[sym[],TraditionalForm];

    (* Autloading can cause a symbol to become protected *)
    Unprotect[sym];

    (* Insert new values in front *)
    Replace[
        new,
        Rule[values_, n_] :> insertValues[n, values, sym],
        {2}
    ];
    Protect@protect;
]

insertValues[n_, v_, sym_] := If[n =!= {},
    v[sym] = DeleteDuplicatesBy[
        Join[n, v[sym]],
        equivalenceClass
    ]
]

equivalenceClass[lhs_ :> rhs_] := If[FreeQ[Hold[rhs], Condition],
    lhs,
    lhs :> rhs
]

A few comments.

  1. I use Language`ExtendedDefinition because it returns all the *Values definitions, and so I can pick off the one that changed, and prepend the new definition to the right *Values function.

  2. I automatically unprotect (and if needed, reprotect) the symbol so that the function will work with Protected symbols.

  3. (updated) I include the lines sym; and MakeBoxes[sym[], TraditionalForm]; so that any package autoloading for sym occurs before I prepend the new *Value. Using sym; causes autoloading of DownValues and UpValues as necessary, while MakeBoxes[sym[], TraditionalForm] causes autoloading of FormatValues. Previously I just used sym; but that didn't cause FormatValues to be autoloaded. Forcing autoloading before creating the *Values is necessary, otherwise the autoloading can occur after the new *Value is added, possibly reordering the *Values so that the new *Values is not in the first position.

  4. (updated) I also added another Unprotect[sym], because some autoloading packages cause the symbol to get reprotected.

  5. (updated) My second update deletes duplicates *Values.

Now, let's see it in action:

Clear[f];
f[x_?EvenQ]:= x;
f[x_?OddQ]:= x^2;
Initial[f] /: f[x_] := Sin[x]

Let's check the DownValues of f:

DownValues[f]

{HoldPattern[f[x_]] :> Sin[x], HoldPattern[f[x_?EvenQ]] :> x, HoldPattern[f[x_?OddQ]] :> x^2}

Sure enough, it is first, and the desired OP output is obtained:

{f[1], f[2], f[3], f[4], f[3/2], f[Newton]} 

{Sin[1], Sin[2], Sin[3], Sin[4], Sin[3/2], Sin[Newton]}

$\endgroup$
  • 1
    $\begingroup$ +1. This answer is actually based on the same set of ideas as this old answer of mine - namely, blocking the symbol and cloning definitions. Your code is in some ways better, however. $\endgroup$ – Leonid Shifrin Aug 17 '17 at 18:47
  • $\begingroup$ @LeonidShifrin Thanks. I actually searched for that question, but couldn't find it, so I added an answer to this question instead. I do like the way I packaged up the answer, but of course, much of the credit should go to LLlAMnYP and Taliesin Beynon. $\endgroup$ – Carl Woll Aug 17 '17 at 19:22
5
$\begingroup$

Thanks to LLlAMnYP's comment (and Jason B's example of it) I've determined the best solution to my situation would be:

In[1]:= Clear[f];
In[2]:= f[x_?EvenQ] := x;
In[3]:= f[x_?OddQ] := x^2;
In[4]:= DownValues[f]=Prepend[DownValues@f, HoldPattern[f[x_]] :> Sin[x] ];
In[5]:= DownValues[f]
Out[5]:= {HoldPattern[f[x_]] :> Sin[x], HoldPattern[f[x_?EvenQ]] :> x, 
HoldPattern[f[x_?OddQ]] :> x^2}

As can be seen, the Sin rule would be tried first even though it is not the most specific (the effect is the same as in Jason B's answer). The Reason this is any different than Jason B's answer is that in this implementation you don't need any information of the existing DownValues of f, as well as being much shorter for more intricate cases.

Thanks a bunch!

Lior

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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