Recursive update of arbitrarily nested dicts

[Ype Kingma]

maxm wrote:
> 
> I am writing a module where I am updating nested dicts, and it has this
> method:
> 
>     def addDayToTrack(self, trackId, year, theDay, day):
>         if not self.tracks.has_key(trackId):
>             self.tracks.update({trackId:{year:{theDay:day}}})
>         elif not self.tracks[trackId].has_key(year):
>             self.tracks[trackId].update({year:{theDay:day}})
>         elif not self.tracks[trackId][year].has_key(theDay):
>             self.tracks[trackId][year][theDay] = day
> 
> oh and self.tracks={}
> 
> But clearly this could be solved more generally by a recursive function.
> Something like:
> 
> def addDayToTrack(self, trackId, year, theDay, day):
>     # recursive update
>     self.rUpdate(self.tracks, {trackId:{year:{theDay:day}}})
> 
> Now my only problem is that recursive method "rUpdate(targetDict,
> itemDict)".
> 
> Knowing this group, many other has written a method like this before me.
> Does anybody have one at hand?
> 
> The idea is that it should traverse the targetDict, updating keys and values
> as apropriate.
> 
> Anyhoo ... I will try it myself, but recursion is not my pot of tea though.
> 
> regards Max M

It's a while ago that I did recursion, and I know beforehand that better
solutions will be posted.

In general recursion has 4 ingredients:
- check for simple (non recursive) case and handle it
- divide problem into smaller problem(s)
- recurse on the smaller problem(s)
- create the solution from the solution(s) to the smaller problem(s).

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 to recurse on
            nestedDict[firstKey] = {}
        rUpdate(nestedDict[firstKey], remainingKeys, value) # recurse on smaller problem.

This happens to be tail recursion, because the solution ends in a recursive call.
Compilers can do nice things to simplify tail recursion to a loop.
(I wonder whether there is such a compiler for python already.)

Have fun,
Ype