# How can I make a “self-referential” replacement operation self-contained?

Fairly often I find use for replacement rules that call themselves on the right-hand side of the rule, e.g.:

rule = {p___, a, b, c, q___} :> Join[{p, "abc"}, {q} /. rule];


Unfortunately this makes the rule dependent on the specific definition of the Symbol rule; it can no longer be copied and modified as an independent expression. Ideally I would like to use the #0 syntax for Function to call the replacement but the most direct application does not work:

# /. {p___, a, b, c, q___} :> Join[{p, "abc"}, #0 @ {q}] & @ "x"


RuleDelayed::rhs: Pattern p___ appears on the right-hand side of rule {p___,a,b,c,q___}:>Join[{p,abc},(#1/. {p___,a,b,c,q___}:>Join[{p,abc},#0[{<<1>>}]]&)[{q}]]. >>

Due to the specific mechanism of #0 its substitution cannot be delayed using e.g. Slot @@ {0}; the substitution will never occur.

The only pseudo-solution I have found is to move #0 out of the RHS of the rule, then substitute it using another replacement:

# /. {p___, a, b, c, q___} :> "Join"[{p, "abc"}, "#0" @ {q}] /. {"Join" -> Join, "#0" -> #0} & @
{1, 2, a, b, c, 3, {4, a, b, c}, 5}

 {1, 2, "abc", 3, {4, "abc"}, 5}


However this destroys the purpose of my construct which was to avoid repeatedly scanning from the beginning of the expression. (There are other uses for self-referential replacement but I believe they are all seriously degraded by this "solution.") It is also fragile to use replacement of "Join" and "#0" so additional complexity or dependency would be required.

Is there some other way I can shield the replacement rule (substituted for #0) from itself without changing the replacement traversal of the expression?

Is there an approach not involving #0 to accomplish my goal?

foo = With[{f = #0}, (# /. {p___, a, b, c, q___} :> Join[{p, "abc"}, f @ {q}])] &

lst = {1, 2, a, b, c, 3, {4, a, b, c}, 5};
foo@lst
(* {1, 2, "abc", 3, {4, "abc"}, 5} *)


This works because With automatically renames the patterns used in RuleDelayed since both are scoping constructs. Other constructs can be used as well such as RuleDelayed itself:

#0 /. f_ :> (# /. {p___, a, b, c, q___} :> Join[{p, "abc"}, f @ {q}]) & @
{1, 2, a, b, c, 3, {4, a, b, c}, 5}

(* {1, 2, "abc", 3, {4, "abc"}, 5} *)


To further illustrate here is an excerpt from TracePrint on the first application above:

 {1, 2, a, b, c, 3, {4, a, b, c}, 5} /. {p$___, a, b, c, q$___} :>
Join[{p$, "abc"}, (With[{f = #0}, #1 /. {p___,a,b,c,q___} :> Join[{p, "abc"}, f[{q}]]]&)[{q$}]]

• Thanks for solving this for me. I wish I had seen the solution myself but it didn't even cross my mind. – Mr.Wizard Aug 14 '14 at 20:01
• @kguler You make me speechless :) Just for curiousity: How could a solution for this brainteaser look like without the Replace-family ? – eldo Aug 14 '14 at 20:04
• @Mr.Wizard, my pleasure. I will need 24-48 hours to digest your new construct:) – kglr Aug 14 '14 at 20:05
• @eldo I don't think I understand what you mean. Replace without using Replace? What's the point of that? – Mr.Wizard Aug 14 '14 at 20:14
• @kguler It's exactly the same as your construct except that I used /. instead of With which does the same thing here, even the renaming. – Mr.Wizard Aug 14 '14 at 20:15