Re: /. Hold -> Identity (Was: One more rules + ev<>rol problem)

*To*: mathgroup at smc.vnet.net*Subject*: [mg114174] Re: /. Hold -> Identity (Was: One more rules + ev<>rol problem)*From*: Leonid Shifrin <lshifr at gmail.com>*Date*: Fri, 26 Nov 2010 05:27:42 -0500 (EST)

Hi kj, Two notes on your solution: 1. The rule Hold->Identity is unsafe. What if your mapped function (or the expression you are mapping on) does contain valid Hold-s which should not be removed? Here is one way to make it safer in this particular respect: Module[{map, myHold}, SetAttributes[myHold, HoldAll]; map[f, {a, b, c, d, e}] //. {map[x_, {}] -> {}, map[x_, {y_, z___}] :> myHold[Prepend[map[x, {z}], x[y]]]} /. myHold -> Identity] Since the name myHold is generated by Module and guaranteed to be unique within a single Mathematica session, you won't run into trouble. 2. Efficiency: using Prepend will guarantee that your map will have quadratic complexity in the size of your list, which will make it unusable for larger lists. You can do some benchmarks to verify this point. There are ways to avoid this slowdown, the one most applicable to your situation is probably to use linked lists. They are discussed in many places, including notes by Daniel Lichtblau on efficient data structures in Mathematica http://library.wolfram.com/infocenter/Conferences/321/ ,various MathGroup posts, and also in the book of David Wagner, which you mentioned (excellent choice b.t.w.). I also discussed them here: http://www.mathprogramming-intro.org/book/node525.html For one example of them being practically used, see Wagner's book again. He looks at merge sort (look at the chapter 10.3 - 10.4, pp. 314 - 324, for a really enlightening and detailed discussion). I also played with this example and ended up with somewhat different implementation, using ReplaceRepeated entirely and also achieving the standard N log N complexity (certainly under Wagner's influence): http://groups.google.com/group/comp.soft-sys.math.mathematica/browse_thread/thread/37c39a26b425cfba (you can look at my post there for the implementation and discussion) Regards, Leonid On Thu, Nov 25, 2010 at 1:57 PM, kj <no.email at please.post> wrote: > In <icg6m9$92s$1 at smc.vnet.net> Bob Hanlon <hanlonr at cox.net> writes: > > >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]} > > Thanks, but note that this fails if the function f produces a list. > E.g., if f is List, then the above would yield {a, b, c, d, e}, > whereas Map[List, {a, b, c,d, e}] would yield {{a}, {b}, {c}, {d}, > {e}}. > > In the meantime, I thought of a slight improvement on one of the > solutions I posted before; instead of > > Module[{map}, > map[f, {a, b, c, d, e}] //. { > map[x_, {}] -> {}, > map[x_, {y_, z___}] :> Hold[Prepend][map[x, {z}], x[y]] > } // ReleaseHold > ] > > ...which is closely tailored to the details of this particular problem, > I now prefer the more general approach of wrapping the entire RHS > of the recursive rule in a Hold, and applying a single Hold -> > Identity replacement to the result of the ReplaceAll: > > Module[{map}, > map[f, {a, b, c, d, e}] //. { > map[x_, {}] -> {}, > map[x_, {y_, z___}] :> Hold[Prepend[map[x, {z}], x[y]]] > } /. Hold -> Identity > ] > > I like this better because it can be easily turned into a programming > (meta-)rule. > > In fact, this combination of a liberal use of Hold, followed by a > single /. Hold -> Identity looks to me like a pretty general strategy > for recovering the default evaluation order of expressions that > are built in stages. > > At first I thought that the way to do this was to run the final > result through ReleaseHold, but this doesn't work, because ReleaseHold > releases only one level: > > Module[{map}, > map[f, {a, b, c, d, e}] //. { > map[x_, {}] -> {}, > map[x_, {y_, z___}] :> Hold[Prepend[map[x, {z}], x[y]]] > } // ReleaseHold > ] > > Hold[f[a], > Prepend[Hold[ > Prepend[Hold[Prepend[Hold[Prepend[{}, f[e]]], f[d]]], f[c]]], > f[b]]] > > In contrast, replacing the Hold with Identity takes care of the > problem in one go, which is key. Any solution that gets rid of > the Hold's in stages will run again into the same sort of problem > (essentially, an aberrant order of evaluation) that the Hold's were > brought in to prevent in the first place (e.g. as illustrated by > the last result: upon release, Prepend proceeded to insert f[a] > as the first argument of the next Hold). > > In fact, the more I think of it, the more I'm surprised by the fact > that Mathematica does not have (AFAIK) a built-in way to remove in > one swoop all the Hold's in an expression, irrespective of their > depth, nor mentions any way to do this in the documentation for > Hold or ReleaseHold. Maybe there's some other standard/preferred > way of achieving the same effect. If so, it would be good for this > to be documented more prominently, since building expressions > piecemeal, unhindered by premature evaluations, seems like a useful > thing to be able to do. > > ~kj > >

**Problems with Mathematica 8.0 Solve**

**Re: New to Mathematica**

**/. Hold -> Identity (Was: One more rules + ev<>rol problem)**

**Re: /. Hold -> Identity (Was: One more rules + ev<>rol problem)**