# Why doesn't recursive transformation stop when rules no longer match?

In an exercise where I was trying to pick out consecutive words starting with the same letter, i.e. I wanted:

{"foo", "fum", "bar", "car", "case", "zen", "dad", "dose"} -> {{"foo", "fum"}, {"car", "case"}, {"dad", "dose"}}


I came up with the following:

In[1]:= FixedPointList[
# /. {{s___List, w_String, x_String, r___} /;
StringTake[w, 1] == StringTake[x, 1] :> {s, {w, x}, r},
{s___List, w_String, x_String, r___} :> {s, x, r},
{s___List} :> {s}} &,
{"foo", "fum", "bar", "car", "case", "zen", "dad", "dose"}]

Out[1]= {{"foo", "fum", "bar", "car", "case", "zen", "dad",
"dose"}, {{"foo", "fum"}, "bar", "car", "case", "zen", "dad",
"dose"}, {{"foo", "fum"}, "car", "case", "zen", "dad",
"dose"}, {{"foo", "fum"}, {"car", "case"}, "zen", "dad",
"dose"}, {{"foo", "fum"}, {"car", "case"}, "dad",
"dose"}, {{"foo", "fum"}, {"car", "case"}, {"dad",
"dose"}}, {{"foo", "fum"}, {"car", "case"}, {"dad", "dose"}}}


While that worked, I initially didn't think I needed the last rule, {s___List} :> {s}, but without that rule FixedPointList doesn't exit as the resulting list never stops changing. This can be seen in a modified version of the above with that rule omitted and using NestList.

In[2]:= NestList[
# /. {{s___List, w_String, x_String, r___} /;
StringTake[w, 1] == StringTake[x, 1] :> {s, {w, x}, r},
{s___List, w_String, x_String, r___} :> {s, x, r}} &,
{"foo", "fum", "bar", "car", "case", "zen", "dad", "dose"}, 10]

Out[2]= {{"foo", "fum", "bar", "car", "case", "zen", "dad",
"dose"}, {{"foo", "fum"}, "bar", "car", "case", "zen", "dad",
"dose"}, {{"foo", "fum"}, "car", "case", "zen", "dad",
"dose"}, {{"foo", "fum"}, {"car", "case"}, "zen", "dad",
"dose"}, {{"foo", "fum"}, {"car", "case"}, "dad",
"dose"}, {{"foo", "fum"}, {"car", "case"}, {"dad",
"dose"}}, {{{"foo", "fum"}}, {{"car", "case"}}, {{"dad",
"dose"}}}, {{{{"foo", "fum"}}}, {{{"car", "case"}}}, {{{"dad",
"dose"}}}}, {{{{{"foo", "fum"}}}}, {{{{"car",
"dose"}}}}}, {{{{{{"foo", "fum"}}}}}, {{{{{"car",
"dose"}}}}}}, {{{{{{{"foo", "fum"}}}}}}, {{{{{{"car",


It's not clear to me why the nested pairs keep getting deeper and deeper after all the pairs are found. I would think that no rule should match after that point and the result should therefore stop transforming. What am I missing?

• Rules don't care how deeply nested it is. It will find a match at any level in an expression. Personally I'd use SplitBy for the task. – wxffles May 17 '16 at 20:28
• The method above is not very efficient, it seems. I re-implemented this using Partition and Select and got quite an improvement. How would you achieve the same output using SplitBy? – Adrian May 18 '16 at 15:01
• @wxffles if you don't mind, you can show an example at this new question I created. – Adrian May 18 '16 at 15:15

One way to debug what's going on is to limit how many times FixedPointList can iterate (which the OP shows in another form).

FixedPointList[# /. {{s___List, w_String, x_String, r___} /;
StringTake[w, 1] == StringTake[x, 1] :> {s, {w, x}, r},
{s___List, w_String, x_String, r___} :> {s, x, r}(*,
{s___List}\[RuleDelayed]{s}*)} &,
{"foo", "fum", "bar", "car", "case", "zen", "dad", "dose"},
7]
(*
{{"foo", "fum", "bar", "car", "case", "zen", "dad", "dose"},
{{"foo", "fum"}, "bar", "car", "case", "zen", "dad", "dose"},
{{"foo", "fum"}, "car", "case", "zen", "dad", "dose"},
{{"foo", "fum"}, {"car", "case"}, "zen", "dad", "dose"},
{{"foo", "fum"}, {"car", "case"}, "dad", "dose"},
{{"foo", "fum"}, {"car", "case"}, {"dad", "dose"}},
{{{"foo", "fum"}}, {{"car", "case"}}, {{"dad", "dose"}}},
{{{{"foo", "fum"}}}, {{{"car", "case"}}}, {{{"dad", "dose"}}}}}
*)


One can see that without the last rule, the intended stopping point is still transformed. This is because ReplaceAll (/.) acts on sublists. Without the last rule, the sublists are transformed. However, with the last rule, the whole list is matched and "transformed" to itself. The match of the whole list means that the sublists are not searched for further matches.

An alternative to using the last rule, is to use Replace instead of ReplaceAll.

FixedPointList[
Replace[#, {{s___List, w_String, x_String, r___} /;
StringTake[w, 1] == StringTake[x, 1] :> {s, {w, x}, r},
{s___List, w_String, x_String, r___} :> {s, x, r}}
] &, {"foo", "fum", "bar", "car", "case", "zen", "dad", "dose"}]
(*
{{"foo", "fum", "bar", "car", "case", "zen", "dad", "dose"},
{{"foo", "fum"}, "bar", "car", "case", "zen", "dad", "dose"},
{{"foo", "fum"}, "car", "case", "zen", "dad", "dose"},
{{"foo", "fum"}, {"car", "case"}, "zen", "dad", "dose"},
{{"foo", "fum"}, {"car", "case"}, "dad", "dose"},
{{"foo", "fum"}, {"car", "case"}, {"dad", "dose"}},
{{"foo", "fum"}, {"car", "case"}, {"dad", "dose"}}}
*)