Nested string substitutions

[Mike Meyer]

Lulu of the Lotus-Eaters <mertz at gnosis.cx> writes:

> I think I am being daft here.  But I cannot think of an elegant way to
> perform a nested expansion of a set of substitution patterns.

I can, but I think it's more work than doing it the straightforward
way.

> I can assume that there is no mutual recursion of substitutions to make
> thing blow up.

That helps.

> I know I can do this with a while loop and a "nothing_left_to_do"
> monitor variable, and some nested '.items()' loops.  But that looks like
> a mess.  It really seems like I should be able to do this with one or
> two lines of an amazing listcomp or map().

There are two things wrong with your intuition here. First,
string.replace generates a new string instead of updating the string
it's invoked on in place. That means you need to do an assignment to
capture the new string. Since assignments aren't expressions, that
pretty much lets out map() and listcomp. You could create a subclass
of string where replace was a procedure instead of a function, but I
don't think you want to go to those extremes.

Second, it takes an indeterminate number of passes over each string to
complete the replacement. Ok, you can do it in one pass - if you do it
in the right order. Maybe that's what was tickling your intuition.
Figuring the right order out requires a topological sort of the items
in the dictionary, which is probably more work than doing the
expansion.  So we'll say it takes an indeterminate number of passes
over the string.

Since map and listcomp only perform one pass, any expression using
them is going to contain a fixed number of passes. If you're willing
to limit the number of expansions, you can do it with that. But I'm
sure that's not what you want.

Alternatives - well, we all know what you need if you want another
way of spelling LOOP.

I'm pretty sure you could use Icon's version of generators to do this
- after all, they can print all the solutions to the 8 queens problems
without a loop. So you might be able to use Pythons generators for
this problem.

Finally, expanding just one string isn't all that ugly. This will do
it:

def expand(key, dict):
    previous = ""
    while previous != dict[key]:
        previous = dict[key]
        for old, new in dict.items():
            dict[key] = dict[key].replace(old, new)

So you can just iterate over the keys of the dictionary with whatever
way of spelling loop you like. Since you wanted a map, my test code
did it this way: map(lambda x: expand(x, subs), subs.keys())

        <mike
-- 
Mike Meyer <mwm at mired.org>			http://www.mired.org/home/mwm/
Independent WWW/Perforce/FreeBSD/Unix consultant, email for more information.