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
>>
>>