MathGroup Archive 2010

[Date Index] [Thread Index] [Author Index]

Search the Archive

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

Hi Leonid.  Thanks for your comments and for the useful links!


In <ico22m$nfg$1 at> Leonid Shifrin <lshifr at> 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


>,various MathGroup posts, and also  in the book of David Wagner,
>which you mentioned (excellent choice b.t.w.). I also discussed them here:


>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
>different implementation, using ReplaceRepeated entirely and also  achieving
>the standard
>N log N complexity (certainly under Wagner's influence):


>(you can look at my post there for the implementation and discussion)


>On Thu, Nov 25, 2010 at 1:57 PM, kj < at> wrote:

>> In <icg6m9$92s$1 at> Bob Hanlon <hanlonr at> 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

  • Prev by Date: Reasons for a two-dimensional layout (was Re: Mathematica 8 docs online now!)
  • Next by Date: Re: Finding local maxima in multidimensional array (efficiently)
  • Previous by thread: Re: /. Hold -> Identity (Was: One more rules + ev<>rol problem)
  • Next by thread: Re: FinancialDerivative Ver 8 (Bug maybe)