Nested string substitutions

[holger krekel]

Lulu of the Lotus-Eaters wrote:
> 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.

Originally i wanted to finish some client work but got distracted
by your mail :-)

> For example, let's say I have a dictionary of patterns:
> 
>     subs = {'foo':'bar baz',
>             'bar':'bat bam ber',
>             'baz':'zat zam zer',
>             'bam':'yat yam yer',
>             'yam':'spam and eggs'}
> 
> I want to "fully expand" the substitution dictionary, getting:
> 
>     subs = {'foo':'bat yat spam and eggs yer ber zat zam zer',
>             'bar':'bat yat spam and eggs yer ber',
>             'baz':'zat zam zer',
>             'bam':'yat spam and eggs yer',
>             'yam':'spam and eggs'}
> 
> I can assume that there is no mutual recursion of substitutions to make
> thing blow up.

i came up with three solutions of which i quote two here:

One is subclassing dict (which may be nice if you want to add
other stuff):

class sdict(dict):
    def subst(self, k=None):
        try: self[k] = " ".join(map(self.subst, self[k].split()))
        except KeyError: return k or map(self.subst, self)
        else: return self[k]

used like this:

    d = sdict(subs)
    res = d.subst('foo')  # expand everything neccessary for 'foo'
    d.subst()             # expand everything


or you can use the following function which also modifies in place:

def xget(d, k=None):
    f = lambda x: xget(d,x)
    try:
        d[k] = " ".join(map(f, d[k].split()))
        return d[k]
    except KeyError:
        return k or map(f, d)


Obviously those two are related but subclassing dict is nicer 
for use with 'map' and friends.     

> 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().

I hope the above fits your idea.  I tested it only with your 'subs' 
example dictionaries, btw. 

Now on to bug hunting :-)

yours,

    holger