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