python: generate a 'diff' dictionary out of two nested dictionaries I have written a function diff that takes two nested dictionaries and it computes a difference of their content (what is inside the list) returning a new dictionary. To better explain what I mean by difference here is an example of two input dictionaries:

dep={'cl1': {'to_do': ['bill', 'ann 46.0.1']},
     'cl2': {'to_do': ['ann 2.2.3']},
     'cl3': {'to_do': ['bill 2.4']}}

ins={'cl1': {'present': ['bill', 'ann 46.0.1', 'ann 2.2.3']},
     'cl2': {'present': ['ann 2.2.3','joy 6.9','matt 6.9']},
     'cl3': {'present': ['bill 2.4']}}


The diff function compares, for each key (cl1 with cl1,cl2 with cl2 and so on...), the present list of ins with the to_do list of dep. If an item of the present list does not appear in the to_do list for a specific key than this item will be added to a list in the output dictionary. If the item found in the present is already in to_do than None will be added to the list. The function returns a dictionary having the same structure as the input dictionaries. Only the names appearing in the list are taken, i.e. no numbers after the names.    

For instance the diff function applied to the case above will give:

out = diff(ins,dep)
out = {'cl1': {'to_uninstall': ['ann']},
       'cl2': {'to_uninstall': ['joy', 'matt']},
       'cl3': {'to_uninstall': [None]}}


Below is the function I am using:

def diff(installed, deploy):
    answer = {}
    #ls_uninst=[]
    for ki,vi in installed.iteritems():
        for kd, vd in deploy.iteritems():
            if ki == kd:
                for ki1, vi1 in vi.iteritems():
                    for kd1, vd1 in vd.iteritems():
                        ls_uninst = []
                        # check if the list is empty
                        if not vi1 :
                            answer[ki] = {}
                            answer[ki]['to_uninstall'] = [None]
                        # non empty list
                        else:
                            for i in vi1:
                                if i not in vd1:
                                    # this gives only the name of the package (not the version)
                                    ls_uninst.append(i.split()[0]) # use i only to get the full name
                                elif i in vd1:
                                    ls_uninst.append(None)
                                # Check if lists contains only None
                                if all(x is None for x in ls_uninst):
                                    answer[ki] = {}
                                    answer[ki]['to_uninstall'] = [None]
                                else: # If at least one package is found
                                    ls_final = [x for x in ls_uninst if x is not None]
                                    answer[ki] = {}
                                    answer[ki]['to_uninstall'] = ls_final
    return answer


It works but I guess this could improved..how? Thanks
To start I'd change the way that you find vd. Instead of looping through the dictionary and checking the keys are the same, just do a lookup of the key.
This may raise a KeyError, and so you'll want to put a guard in for that.

However the rest of your code needs to change.
First if we have a look at your for i in vi1 loop.
You have the comment Check if lists contains only None, but you're making that list?
Don't do this. Ever.
And so I would move the if and else out of that loop:

for i in vi1:
    if i not in vd1:
        ls_uninst.append(i.split()[0])
    elif i in vd1:
        ls_uninst.append(None)

if all(x is None for x in ls_uninst):
    answer[ki] = {}
    answer[ki]['to_uninstall'] = [None]
else:
    ls_final = [x for x in ls_uninst if x is not None]
    answer[ki] = {}
    answer[ki]['to_uninstall'] = ls_final


From this we can see that the for loop should probably be a comprehension, and I'm saying this now [None] is horrible, so I'm removing that from here.
Which would result in:

ls_uninst = [i.split()[0] for i in vi1 if i not in vd1]


After this, you should be able to see that if not vi1 is true not ls_uninst is true too, and so you can merge these ifs.
Resulting in something like:

for kd1, vd1 in vd.iteritems():
    ls_uninst = [i.split()[0] for i in vi1 if i not in vd1]
    answer[ki] = {}
    if ls_uninst:
        answer[ki]['to_uninstall'] = ls_uninst
    else:
        answer[ki]['to_uninstall'] = [None]


The if can then become either a ternary, or you can use or. I think or is quite nice here.
But to be honest, you should just remove this if.

You should now have something that looks like:

def diff(installed, deploy):
    answer = {}
    for ki, vi in installed.iteritems():
        try:
            vd = deploy[ki]
        except KeyError:
            continue
        for ki1, vi1 in vi.iteritems():
            for kd1, vd1 in vd.iteritems():
                ls_uninst = [i.split()[0] for i in vi1 if i not in vd1]
                answer[ki] = {}
                answer[ki]['to_uninstall'] = ls_uninst or [None]
    return answer


This only uses the last vi1 and vd1 to create this list.
So you should use itervalues instead.
Also I'd use all of the values, not just the last.
This can be done by flattening vi.itervalues,
I'd do this by using itertools.chain.from_iterable, but ultimately it's up to you.
I'd also change vd1 to a set.
And all of this results in:

from itertools import chain
flatten = chain.from_iterable

def diff(installed, deploy):
    answer = {}
    for ki, vi in installed.iteritems():
        try:
            vd = deploy[ki]
        except KeyError:
            continue
        vi1 = flatten(vi.itervalues())
        vd1 = set(flatten(vd.itervalues()))
        ls_uninst = [i.split()[0] for i in vi1 if i not in vd1]
        answer[ki] = {}
        answer[ki]['to_uninstall'] = ls_uninst or [None]
    return answer