19
$\begingroup$

Consider the following minimal examples. This one works as expected, replacing trees starting from the inside with a numerical value.

ClearAll[tree];
x = tree["A", {tree["B", {1, 2}], 3}];
Replace[x, t_tree :> (Print[t]; 0), {0, Infinity}]

During evaluation of In[1]:= tree[B,{1,2}]  
During evaluation of In[1]:= tree[A,{0,3}]  
Out[1]= 0

This one however introduces an unexpected intermediate step.

Replace[x, t_tree :> (Print[t, t]; 0), {0, Infinity}]

During evaluation of In[3]:= tree[B,{1,2}]tree[B,{1,2}]
During evaluation of In[3]:= tree[B,{1,2}]tree[B,{1,2}]
During evaluation of In[3]:= tree[A,{0,3}]tree[A,{0,3}]
Out[3]= 0

While the results are the same, anything more complicated than Print[t] causes extra stages to appear. Hence I cannot reliably use Replace to collect replaced parts (instead of printing them), as there would be excess entries at the end, see next example:

y = {}; Replace[x, t_tree :> (AppendTo[y, t]; 0), {0, Infinity}]; y

{tree["B", {1, 2}], tree["A", {0, 3}]}

y = {}; Replace[x, t_tree :> (AppendTo[y, t -> Mean@Last@t]; 0), {0, Infinity}]; y

{tree["B", {1, 2}] -> 3/2, tree["B", {1, 2}] -> 3/2, tree["A", {0, 3}] -> 3/2}

There are three replacements instead of two.

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ I hit this problem multiple times, every time having forgotten about the earlier one, and taking a while to understand what was going on. $\endgroup$
    – Szabolcs
    Commented Sep 7, 2016 at 12:05
  • 1
    $\begingroup$ Is that it? When is the righthand side of a RuleDelayed evaluated? $\endgroup$
    – Kuba
    Commented Sep 7, 2016 at 12:09
  • $\begingroup$ @Kuba Yes, it seems to be a duplicate. $\endgroup$
    – István Zachar
    Commented Sep 7, 2016 at 12:18

1 Answer 1

Reset to default
22
$\begingroup$

This is not a bug. However, this is a great opportunity to shed some light on the inner workings of Replace. What happens, in short, is that it first fully processes the expression, without calling main evaluator on any of its replaced parts, and only then the entire transformed expression is given to the evaluator.

Basically, we can visualize what happens using this:

held = Replace[Hold[Evaluate[x]],t_tree :> (Print[t, t]; 0), {0, Infinity}]


(* 
  Hold[
    Print[tree["A", {Print[tree["B", {1, 2}], tree["B", {1, 2}]]; 0, 3}],
    tree["A", {Print[tree["B", {1, 2}], tree["B", {1, 2}]]; 0, 3}]]; 0
  ]
*)

which shows the origin of extra Print.

What you were assuming was that the evaluation of replaced parts happens right after they were replaced, which would mean that Replace would have to call main evaluator after replacement at each level. Instead, the action of Replace is semantically equivalent to

ReleaseHold[Replace[Hold[expr], rules, spec]]

which may produce different result if side effects are injected by replacement rules.

Improve this answer
$\endgroup$
7
  • $\begingroup$ Well, I had the suspicion, that there shouldn't be a bug in a core function, and I'm glad I was cautious with the tagging. Thanks for the explanation! Do you also have a suggestion how to robustly solve what I want to do: depth-first sequential replacement from inside-out with storing actual replacements by AppendTo or Sow? $\endgroup$
    – István Zachar
    Commented Sep 7, 2016 at 12:14
  • 1
    $\begingroup$ @IstvánZachar You could write your own expression parser, that would do expression traversal. Or use something like Fold[Replace[#, rules, {#2}]&, expr, Reverse[Range[Length[Depth[expr]]]]] (pseudocode, untested). $\endgroup$
    – Leonid Shifrin
    Commented Sep 7, 2016 at 13:14
  • 2
    $\begingroup$ @IstvánZachar Another possibility might be to force early evaluation using one of the techniques described in Replacement inside held expression. For example: Replace[x, t_tree :> With[{}, Print[t, t]; 0 /; True], {0, Infinity}]. $\endgroup$
    – WReach
    Commented Sep 8, 2016 at 11:52
  • 1
    $\begingroup$ Thanks @Leonid, I ended up using the reversed-level-scan method, which I already used in other cases but forgot about. Somewhat hoped maybe there is a new function capable of this natively in v11 that I missed. Just for the record, the level specification should rather be Range[Depth[expr], 0, -1] if I'm not mistaken. $\endgroup$
    – István Zachar
    Commented Sep 8, 2016 at 18:40
  • 1
    $\begingroup$ @WReach I think that the applicability of the Trott-Strzebonski trick to Replace is so unobvious that it is worth to post this as a separate answer. Also this example (along with Leonid's explanation) is very enlightening for understanding the essence of the trick itself. $\endgroup$
    – Alexey Popkov
    Commented Sep 17, 2016 at 11:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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