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

*To*: mathgroup at smc.vnet.net*Subject*: [mg114228] Re: /. Hold -> Identity (Was: One more rules + ev<>rol problem)*From*: kj <no.email at please.post>*Date*: Sun, 28 Nov 2010 06:52:15 -0500 (EST)*References*: <ico22m$nfg$1@smc.vnet.net>

Hi Leonid. Thanks for your comments and for the useful links! ~kj In <ico22m$nfg$1 at smc.vnet.net> Leonid Shifrin <lshifr at gmail.com> writes: >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 >> >>