One more rules + evaluation control problem

*To*: mathgroup at smc.vnet.net*Subject*: [mg114033] One more rules + evaluation control problem*From*: kj <no.email at please.post>*Date*: Sat, 20 Nov 2010 18:28:37 -0500 (EST)

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!