Home Original page

Recursive update of arbitrarily nested dicts

Ype Kingma ykingma at accessforall.nl
Sun Dec 16 06:36:49 EST 2001 
maxm wrote:
> 
> "Ype Kingma" <ykingma at accessforall.nl> wrote in message
> news:3C1B9E80.FB732387 at accessforall.nl...
> 
> > In this case there is only one smaller problem, and there is no
> > solution to be assembled from the solutions to the smaller problem.
> > (warning: untested code)
> >
> > def rUpdate(nestedDict, keys, value): # keys should be a tuple or a list
> >     firstKey, remainingKeys = keys[0], keys[1:] # divide the problem
> >     if len(remainingKeys) == 0: # non recursive case
> >         # Evt. raise an exception when nestedDict[firstKey] is a dict
> >         nestedDict[firstKey] = value # actual update.
> >     else:
> >         if not nestedDict.has_key[firstKey]: # make sure there is sub dict

Should be:  if not nestedDict.has_key(firstKey): # make sure there is sub dict

> >             nestedDict[firstKey] = {}
> >         rUpdate(nestedDict[firstKey], remainingKeys, value) # recurse on
> smaller problem.
> 
> whoa ... thats a pretty complex solution. I was hoping for something a bit
> simpler ;-)

The solution you give below is a bit more complex, although it does not show
up in the number of lines of code.
I never got the hang of setdefault(), so I basically coded it in full.
Your solution needs a dictionary to update from, mine allows only a single key set.
It also has a self argument, which I avoided.

> 
> In fact I do belive that I have found it myself, after an hour of fun. ;-)
> 
>     def rUpdate(self, targetDict, itemDict):
>             for key, val in itemDict.items():
>                 if type(val) == type({}):
>                     newTarget = targetDict.setdefault(key,{})
>                     self.rUpdate(newTarget, val)
>                 else:
>                     targetDict[key] = val
> 
> I allways find it amusing that recursive functions in Python ends up so
> relatively simple, even though I usually have a bit of a problem finding the
> right solution.
> 

In Python it is natural to avoid a lot of recursion by using a for loop instead.

> I have read somewhere that thinking in pointers is something a programmer
> either can or cannot do. I have no trouble with pointers. But perhaps it's
> the same with recursion ... I don't know. I can usually find a solution, but
> it often takes me far to long. I guess if I do it more I will get better at
> it. Perhaps I should study some Lisp to get some more experience in it.
> 

There's a nice overview here:

http://www.cs.sfu.ca/~cameron/Teaching/384/99-3/recursion.html

> Anyhoo ... Thanks for the answer.
>
 
My pleasure,
Ype
More information about the Python-list mailing list