I'm trying to use ReplaceList to match subexpressions. I expected the command:

ReplaceList[{p, {p, p}}, {x_, y_} -> x y]

to output two results, equivalent to: p {p, p} and {p, p p}. That's because I expect the rule {x_,y_} to match both {p,{p,p}} and {p,p}. Only one result is output, equivalent to p {p,p}. I suppose that this is because ReplaceAll's behavior of replacing all subexpressions is special, whereas the default Replace that ReplaceList must use, only matches against the first level of the rule.

That's great, but how can I get the functionality I expect? I need this to apply to arbitrary levels of nesting. For example, I would expect it to turn {p, {p, {p, p}}} into

{ p {p, {p, p}}, {p, p {p, p}}, {p, {p, p p}} }

(I'm trying to reproduce the work on page 781 of the New Kind of Science book, in which subexpressions of Nand tautologies are matched/replaced according to the rules on page 775).

  • $\begingroup$ ReplaceList[{p, {p, p}}, {{x_, y_} -> x y, {x_, y_} :> {x, Times @@ y}}] $\endgroup$
    – ciao
    Apr 7, 2014 at 1:29
  • $\begingroup$ @rasher yes, that works for the case I gave, but it doesn't turn {p, {p, {p, p}}} into { {p {p, {p, p}}}, {p, p {p, p}}, {p, {p, p p}} }. Sorry for not being clear what I meant by "arbitrary levels of nesting". $\endgroup$
    – user273
    Apr 7, 2014 at 1:36
  • 1
    $\begingroup$ NKS book has code of its examples - it's at the end: For p.775 - p.1155 For p.781 - p.1157 BTW whatever essential info your add in the comments - you shoudl add it to your post too. $\endgroup$ Apr 7, 2014 at 1:36
  • $\begingroup$ @VitaliyKaurov, p. 1157 states that "every possible transformation rule is applied wherever it can", but doesn't give an implementation. There's code on 1157, but this only generates the longest statement of its kind at every step. p. 1155 states the substitution rules I need to use, but I'm not sure how to apply one substitution rule in every possible way, at every level of the expression. $\endgroup$
    – user273
    Apr 7, 2014 at 1:47
  • 1
    $\begingroup$ @NeuroFuzzy: Ah, well, you could define transformations and use MapAll, or Fold over replacement rules. Not 100% certain ReplaceList alone will do what you want. $\endgroup$
    – ciao
    Apr 7, 2014 at 2:04

1 Answer 1


One method I've found that works, at least for this case, is to use Position and MapAt:

myReplaceListAll[l_, rule_] := 
 MapAt[Function[x, Replace[x, rule]], l, #] & /@ 
  Position[l, rule[[1]] ]

This almost works, except that when Position matches the whole list it returns {}, and MapAt doesn't return the whole expression. list

rule = ({x_, y_} -> x y);
list = {p, {p, p}};
MapAt[f, list, #] & /@ Position[list, rule[[1]]]


{{p, f[{p, p}]}, {p, {p, p}}}

So in this case, to get everything to work exactly as intended, I have to write:

myReplaceListAll[l_, rule_] :=
  If[# != {},
     MapAt[Function[x, Replace[x, rule]], l, #],
     Replace[l, rule]
     ] & /@ Position[l, rule[[1]]];

In[]:= myReplaceListAll[{p,{p,p}},{x_,y_}->x y]
Out[]= {{p,p^2},{p^2,p^2}}

In[]:= myReplaceListAll[{p,{p,{p,p}}},{x_,y_}->x y ]
Out[]= {{p,{p,p^2}},{p,{p^2,p^2}},{p^2,{p^2,p^2}}}

You may also want to add the Heads->False option to the Position command.

  • $\begingroup$ You can workaround the {} case by wrapping list with some intert head, for example by List: (MapAt[f, {list}, #] & /@ Position[{list}, rule[[1]]])[[All, 1]]. $\endgroup$ May 7, 2014 at 10:39

Your Answer

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