Re: Programming: Replace Heads
- To: mathgroup at smc.vnet.net
- Subject: [mg5216] Re: Programming: Replace Heads
- From: Robert Villegas <villegas>
- Date: Fri, 15 Nov 1996 03:22:36 -0500
- Sender: owner-wri-mathgroup at wolfram.com
> Problem:
> Given an abritrary expression, how to replace all heads to List?
This can be done in one command:
Apply[List, expr, {0, -2}]
Here is an example using your random expression generator:
In[1]:= Clear[a,b,c,d,e,f,g]
In[2]:= f := ({a,b,c,d,e,g}[[Random[Integer, {1,6}] ]])
In[3]:= expr = Array[ Hold at f, {3,2,3},1, Hold at f]//ReleaseHold
Out[3]= e[b[b[g[1, 1, 1], c[1, 1, 2], d[1, 1, 3]],
c[d[1, 2, 1], e[1, 2, 2], a[1, 2, 3]]],
a[c[b[2, 1, 1], d[2, 1, 2], b[2, 1, 3]],
d[g[2, 2, 1], b[2, 2, 2], g[2, 2, 3]]],
b[a[e[3, 1, 1], e[3, 1, 2], a[3, 1, 3]],
b[d[3, 2, 1], b[3, 2, 2], a[3, 2, 3]]]]
In[4]:= Apply[List, expr, {0, -2}]
Out[4]= {{{{1, 1, 1}, {1, 1, 2}, {1, 1, 3}},
{{1, 2, 1}, {1, 2, 2}, {1, 2, 3}}},
{{{2, 1, 1}, {2, 1, 2}, {2, 1, 3}}, {{2, 2, 1}, {2, 2, 2}, {2, 2, 3}}},
{{{3, 1, 1}, {3, 1, 2}, {3, 1, 3}}, {{3, 2, 1}, {3, 2, 2}, {3, 2, 3}}}}
The {0, -2} argument says that the head replacement should happen
at all levels of the expression. Specifically, it means the whole
expression (level 0), the elements of the expression (level 1),
the elements of the elements (level 2), and so on, all the way
through subexpressions that are one level above atoms (level -2).
Suppose your expression is a little more complicated, having heads
that are themselves complex expressions. For instance,
In[6]:= Clear[f, g, h, u, v, x, y]
In[7]:= expr = (f + g)[x, y] * h[ u[x], v[x] ]
Out[7]= (f + g)[x, y] h[u[x], v[x]]
In this expression, (f + g) is the head of [x, y]. Perhaps you don't
want (f + g) blown away and replaced by List, but instead treated like
any other expression and turned into the list {f, g}. Here is a
function that will distinguish atomic heads from non-atomic heads:
Listify[atom_?AtomQ] := atom
Listify[h_[elems___] /; AtomQ[h]] := Map[Listify, {elems}]
Listify[h_[elems___]] := Map[Listify, h[elems], Heads->True]
Here's what it does to the more complex expression:
In[11]:= Listify[expr]
Out[11]= {{f, g}[x, y], {{x}, {x}}}
This function recursively applies itself to heads and elements until it
reaches atoms. When it reaches an atomic head, it replaces it by List.
When it reaches an atomic element, it leaves it alone.
A different implementation of that idea uses ReplaceRepeated
(special input form is "//.") to change subexpressions to lists
until there is nothing left that isn't a list or an atom.
In[12]:= Clear[Listify]
In[13]:= Listify[expr_] := expr //. {
atom_?AtomQ :> atom,
h_[elems___] /; AtomQ[h] && h =!= List :> {elems}
}
In[14]:= Listify[expr]
Out[14]= {{f, g}[x, y], {{x}, {x}}}
The test h =!= List is necessary to prevent ReplaceRepeated from
re-transforming subexpressions it has already made into lists. A
subexpression that is already a list would not change under the rule, so
ReplaceRepeated would think the substitution rules are having no further
effect, and it would stop. Preventing ReplaceRepeated from transforming
lists forces it to go inside them in search of things to substitute
(ReplaceRepeated works starts at the top and works down until it finds
something it can replace).
Robby Villegas
P.S. For advanced use on unevaluated expressions, here are
implementations that carefully avoid evaluation. Change HoldAll
to HoldAllComplete in the code below if you have 3.0 and want even
Sequence and Evaluate to be left unevaluated.
(* recursive method *)
Listify[expr_] := listify[expr]
Attributes[listify] = HoldAll
listify[expr_ /; AtomQ @ Unevaluated[expr]] := expr
listify[h_[elems___] /; AtomQ @ Unevaluated[h]] :=
Map[listify, Unevaluated[{elems}] ]
listify[h_[elems___]] := Map[listify, Unevaluated @ h[elems], Heads->True]
(* ReplaceRepeated method *)
Listify[expr_] :=
Module[{HoldingContainer, listified},
Attributes[HoldingContainer] = HoldAll;
listified = HoldingContainer[expr] //. {
atom_ /; AtomQ @ Unevaluated[atom] :> atom,
h_[elems___] /; AtomQ @ Unevaluated[h] &&
!MemberQ[{List, HoldingContainer}, Unevaluated[h]] :> {elems}
};
First[listified]
]
Tests:
In[24]:= Listify[expr]
Out[24]= {{f, g}[x, y], {{x}, {x}}}
In[25]:= Listify @ Unevaluated[(1 * 2) + Print[3, 4]]
Out[25]= {{1, 2}, {3, 4}}
In[26]:= Listify @ Function[{x, y, z}, Print[x, ":", y, "--", z]]
Out[26]= {{x, y, z}, {x, :, y, --, z}}