Re: One more rules + evaluation control problem
- To: mathgroup at smc.vnet.net
- Subject: [mg114077] Re: One more rules + evaluation control problem
- From: Bob Hanlon <hanlonr at cox.net>
- Date: Tue, 23 Nov 2010 05:57:16 -0500 (EST)
Module[{map},
map[f, {a, b, c, d, e}] //. {
map[x_, {}] :> {},
map[x_, {y_, z___}] :> Prepend[{map[x, {z}]}, x[y]]}] // Flatten
{f[a], f[b], f[c], f[d], f[e]}
Bob Hanlon
---- kj <no.email at please.post> wrote:
=============
I'm trying to become more facile with Mathematica patterns and
rules. To this end, I'm doing some exercises from a book (Wagner's
Power Programming with Mathematica, 1996). (Rules programming
doesn't come easily to me, and I'm becoming more and more aware of
how much of a handicap this is when working with Mathematica.)
One exercise is "use sequence matching to write recursive functions
that mimic the functionality of (a) Map, (b) Nest, (c) Fold." This
wasn't too hard:
In[1]:= Module[{map},
map[x_, {}] = {};
map[x_, {y_, z___}] := Prepend[map[x, {z}], x[y]];
map[f, {a, b, c, d}]
]
Out[1]= {f[a], f[b], f[c], f[d]}
In[2]:= Module[{nest},
nest[x_, y_, 0] := y;
nest[x_, y_, n_] /; (IntegerQ[n] && n > 0) := nest[x, x[y], n - 1];
nest[f, a, 5]
]
Out[2]= f[f[f[f[f[a]]]]]
In[3]:= Module[{fold},
fold[f_, x_, {}] := x;
fold[f_, x_, {y_, z___}] := fold[f, f[x, y], {z}];
fold[f, x, {a, b, c, d}]
]
Out[3]= f[f[f[f[x, a], b], c], d]
The next exercise was to redo the previous one, but using instead
what the author calls "the 'pure' rule-based approach", as illustrated
by the following "inline" recursive implementation of the factorial
function:
f[5] //. {f[0] :> 1, f[n_] :> n*f[n - 1]}
120
For Nest and Fold, this task was simply a matter of rearranging
the lines of In[2] and In[3], and changing the SetDelayed's to
RuleDelayed's:
In[4]:= Module[{nest},
nest[f, a, 5] //. {nest[x_, y_, 0] :> y,
nest[x_, y_, n_] /; (IntegerQ[n] && n > 0) :> nest[x, x[y], n - 1]}
]
Out[4]= f[f[f[f[f[a]]]]]
In[5]:= Module[{fold},
fold[f, x, {a, b, c, d}] //. {fold[f_, x_, {}] :> x,
fold[f_, x_, {y_, z___}] :> fold[f, f[x, y], {z}]}
]
Out[5]= f[f[f[f[x, a], b], c], d]
For Map, however, this simple strategy fails when applied to the
definition in In[1]:
In[6]:= Module[{map},
map[f, {a, b, c, d, e}] //. {map[x_, {}] -> {},
map[x_, {y_, z___}] :> Prepend[map[x, {z}], x[y]]}
]
Out[6]= map$1045[f[a], f, {b, c, d, e}]
The reason is that Prepend (and Join, Append, etc.) work on
expressions having any head (including, e.g., map$1045 above), not
just List. Therefore, I don't see how I can *directly* extend my
original recursive scheme for map (In[1]) into this "pure" rule-based
form (by "directly" I mean without adding to it some patch or other
(e.g. Hold[Prepend], etc., wholly extraneous to the solution in
In[1]).
Since this second exercise was so simple for Nest and Fold, I
conclude that there must be some *other* way, different from the
one in In[1], to use sequence matching to define a recursive function
that mimics Map *and* that can be as easily adapted to the "pure"
rule-based approach as In[2] (for nest) and In[3] (for fold) were.
Does anyone know what such alternative (sequence-matching recursive)
implementation of Map would be?
Note: I *have* found several ways to patch the "pure" rule-based
map in In[6] so that it produces the correct result, at the expense
of increased complexity (i.e. the "extraneous" patches I alluded
to above). I have also implemented a function that mimics Map much
more closely than either In[1] or the fixed versions of In[6],
although it is neither recursive, nor purely rule-based (see below).
My question in this post is one specifically about rules programming
technique: is there a sequence-matching recursive Map-mimicking
function that can be directly converted to a "pure" rule-based
definition, in the way that the nest and fold in In[2] and In[3]
were converted to In[4] and In[5], respectively? As I said at the
beginning of this post, my primary aim is not to solve these
exercises, but to get better with rules and patterns.
TIA!
~kj
PS: here are some alternative definitions of map:
In[7]:= Module[{map},
map[f, {a, b, c, d, e}] //. {map[x_, {}] -> {},
map[x_, {y_, z___}] :> Hold[Prepend][map[x, {z}], x[y]]} //
ReleaseHold
]
Out[7]= {f[a], f[b], f[c], f[d], f[e]}
In[8]:= Module[{map, prepend},
map[f, {a, b, c, d, e}] //. {map[x_, {}] -> {},
map[x_, {y_, z___}] :> prepend[map[x, {z}], x[y]],
prepend[{x___}, y_] :> {y, x}}
]
Out[8]= {f[a], f[b], f[c], f[d], f[e]}
Nevertheless, neither of In[1], In[7], and In[8] comes close to
matching Map's full functionality. The following definition (which
does not use any of the techniques mentioned above) comes much
closer to Map (the key rule is the one that uses Replace):
In[9]:= map[f_, x_?AtomQ, opts___?OptionQ] := x
map[f_, e_, opts___?OptionQ] := map[f, e, 1, opts]
map[f_, e_,
ls : (_Integer | {_Integer} | {_Integer, _Integer} |
Infinity | {_Integer, Infinity}), opts___?OptionQ] :=
Replace[e, x_ :> f[x], ls, opts]
map[x___ /;
Length[{x}] == 0 &&
Message[map::argt, HoldForm[map], HoldForm[0], HoldForm[2],
HoldForm[3]] && False] = Null
map[_ /; Message[map::argtu, HoldForm[map], HoldForm[2],
HoldForm[3]] && False] = Null
map[x : PatternSequence[_, _, _], y_, z___] /;
Message[map::nonopt, HoldForm[y], HoldForm[3],
HoldForm[map[x, y, z]]] && False = Null
The only way I know of in which In[9] does not behave like Map is
that it can't handle SparseArrays. (I don't yet understand the
SparseArray representation sufficiently well to implement this
extension.)
The map in In[9] is my most ambitious rules-based function definition
to date. It took a lot of time and a lot of trial-and-error to
write, and I learned a lot in the process. But I'm sure there's
still in it a lot of room for improvement. If you can see such
improvements, or have counterexamples, comments, and constructive
criticism in general, they are always welcome!