4
$\begingroup$

I have an expression which I would like to make a position index of, which for sake of argument will be this:

expr = f[q + g[x, y, z]];

Since it's not a list, and I want to build an index at all levels, PositionIndex is not my friend. Still, I have a solution using MapIndexed that's not too terrible and gets me the result I want:

Module[
  {index = <||>},
  MapIndexed[
    (AppendTo[index, #2 -> #1]; #1) &,
    expr,
    {0, Infinity}, Heads -> True];
  index]

 (* <|{0} -> f, {1,0}-> Plus, {1,1} -> q, 
     {1,2,0} -> g, {1,2,1} -> x, {1,2,2} -> y, {1,2,3} -> z,
     {1,2} -> g[x,y,z], {1} -> q+g[x,y,z], {} -> f[q+g[x,y,z]]|>     *)

However, this all goes terribly wrong if I try to index a held expression while keeping things held:

heldExpr = HoldComplete[f[q + g[x, y, z]]];
Module[{index = <||>},
 MapIndexed[
   (AppendTo[index, #2 -> HoldComplete[#1]]; #1) &,
   heldExpr,
   {0, Infinity}, Heads -> True];
 index]
(* <|{0} -> HoldComplete[HoldComplete], 
    {} -> HoldComplete[HoldComplete[((AppendTo[index$248139, #2 -> HoldComplete[#1]];
  [many lines of garble omitted]
*)

I tried the Trott-Strzebonski trick, which did little to improve things:

Module[{index = <||>},
 MapIndexed[
   With[{eval = (AppendTo[index, #2 -> HoldComplete[#1]]; #1)}, 
     eval /; True] &,
 heldExpr,
 {0, Infinity}, Heads -> True];
 index]

(*<|{0} -> HoldComplete[HoldComplete], 
   {1, 0} -> HoldComplete[f], {1, 1, 0} -> HoldComplete[Plus], 
   {1, 1, 1} -> HoldComplete[q], {1, 1, 2, 0} -> HoldComplete[g], 
   {1, 1, 2, 1} -> HoldComplete[x], {1, 1, 2, 2} -> HoldComplete[y], 
   {1, 1, 2, 3} -> HoldComplete[z],
   [here's where it starts going wrong] 
   {1, 1, 2} ->  HoldComplete[(g /; True)[x /; True, y /; True, z /; True]]
   [several more elements where non-atomic expressions have sprouted spurious 
    /; True conditions omitted] |> *)

In principle, I could probably use a rule replacement to strip the /; True stuff, but I don't see a way to do that without destroying legitimate vacuously true conditions (which may well be present in source code for any number of reasons). I suppose I could pre-transform the expression so every True is replaced with a unique symbol and then switch back, but that seems annoying and possibly error prone.

$\endgroup$
5
$\begingroup$

I think, MapIndexed is not really your friend here, because you can't easily force evaluation deep inside held expressions when using the functions of the Map family. The Trott-Strzebonski trick works for rules applied to entire expression, and the way you tried to use that construct could not have worked simply because that was a pure function, not a (r.h.s. of the) rule. OTOH, when rules are applied, they on their own have no information on part's position, which rules out a direct application of TS technique for this problem (pun intended).

Now, to the position index problem proper. I don't see a big advantage in having direct index position -> part, since positions are unique and one can get those parts out simply using Part or Extract. So I will provide a function to build the part -> position-list index, which seems more useful (PositionIndex is doing that too):

positionIndexNested[expr_] :=
  GroupBy[First -> Last] @ Thread[
    {
       Extract[Unevaluated @ expr, # , HoldComplete], 
       #
    } & @ Position[Unevaluated @ expr, _]
  ]

The Unevaluated wrappers were used to enable things like this:

positionIndexNested[Unevaluated[Print[1 + 1, 2 + 2]]]

(* 
  <|
    HoldComplete[Print] -> {{0}}, 
    HoldComplete[Plus] -> {{1, 0}, {2, 0}}, 
    HoldComplete[1] -> {{1, 1}, {1, 2}}, 
    HoldComplete[1 + 1] -> {{1}}, 
    HoldComplete[2] -> {{2, 1}, {2, 2}}, 
    HoldComplete[2 + 2] -> {{2}}, 
    HoldComplete[Print[1 + 1, 2 + 2]] -> {{}}
  |>
*)

For the inverse position index (the one you asked for), simply permute the parts of the list inside Thread, namely Extract[...] and #.

There is a way to use MapIndexed to solve this problem, too, but it is way less direct and will effectively just reimplement the above in a more complex way. You basically first use MapIndexed to map some HoldAllComplete custom wrapper / symbol on all parts of the expression, then use Cases to collect all parts and remove the wrapper in their inner parts. I have the code for that, and can add it upon request, but just see no point.

| improve this answer | |
$\endgroup$
  • 2
    $\begingroup$ +1. In a similar vein: Position[expr, _] // Query[Association, # -> Extract[expr, #, HoldComplete] &] $\endgroup$ – WReach Mar 13 at 23:22
  • $\begingroup$ @WReach Yep, that works too. I instinctively try to avoid Query as I don't view it as a core language construct of the same level as list and assoc operations (i.e. with simple / clear semantics that is guaranteed to stay the same in the future), but I admit that it does sometimes make things a little more concise. $\endgroup$ – Leonid Shifrin Mar 13 at 23:28
  • 1
    $\begingroup$ # -> Extract[expr, #, HoldComplete] & /@ Position[expr, _] // Association if one prefers ;) $\endgroup$ – WReach Mar 13 at 23:30
  • $\begingroup$ @WReach I certainly do :) $\endgroup$ – Leonid Shifrin Mar 13 at 23:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.