Recursive Function to Go Inside Dictionary of Dictionary

Recursive function to go inside dictionary of dictionary

You need just process iterable items(not only dict). Here an example:

import collections

example_data = {
    'apple': 9,
    'ball': {
        'cat': 8,
        'www': (
            'data',
            {
                'new': 'hello',
                'ppp': (
                    'dat',
                    [{'jjj': 'world'}]
                )
            }
        )
    }
}


def get_keys(data, result=None):
    result = result or dict()
    # dict processing
    if isinstance(data, dict):
        for key, value in data.items():
            # not str, but iterable - call get_keys one more time
            if type(value) != str and isinstance(value, collections.Iterable):
                result = get_keys(value, result)
            else:
                # value isn't iterable - just set to result
                result[key] = value
    # list, tuple, set processing
    elif isinstance(data, (list, tuple, set)):
        for item in data:
            # list item is not str, but iterable - call get_keys one more time
            if type(item) != str and isinstance(item, collections.Iterable):
                result = get_keys(item, result)

    return result


print(get_keys(example_data))

Hope this helps.

Python: recursive function to find value in nested dictionary keeps returning 'None'

The issue is UserID is inside ['Metadata']['Core'] which is a list.

You are only recursing if v is a dict.

You could modify your code to handle that:

def lookup(dic, prop):
    for k, v in dic.items():
        if k == prop:
            if not isinstance(v, dict):
                return v
        if isinstance(v, dict):
            return lookup(v, prop)
        if isinstance(v, list):
            for item in v:
                found = lookup(item, prop)
                if found:
                    return found

>>> lookup(metadata_dict, "UserID")
[{'_text': 'xyz'}]

I left out:

else:
    for key, value in v:
        return value

v is a dict, so this should raise an error. Also return will exit the function - so this will only ever process a single value.

If there can be multiple matches - you could use a generator instead.

def lookup(dic, prop):
    for k, v in dic.items():
        if k == prop:
            if not isinstance(v, dict):
                yield v
        if isinstance(v, dict):
            yield from lookup(v, prop)
        if isinstance(v, list):
            for item in v:
                yield from lookup(item, prop)

Output:

>>> for result in lookup(metadata_dict, "UserID"):
...     print(result)
[{'_text': 'xyz'}]

Example with multiple values:

>>> for result in lookup({"Foo": [{"UserID": 1}], "Bar": {"Baz":[{"Hi": {"UserID": "2"}}]}}, "UserID"):
...     print(result)
1
2

Recursive Function through dict of lists

You could iteratively call recurse_over_object under if 'subfolder' in key:. So like:

def recurse_over_object(dict_obj):
    for key, value in dict_obj.items():
        if 'subfolder' in key:
            for item in value:
                recurse_over_object(item)
        else:
            print(key, value)

Then

for d in data:
    recurse_over_object(d)

outputs:

name Business Operations
team_edit ['BusinessOperations']
team_view ['Snaptest']
name test_sub
team_edit ['BusinessOperations', 'Freddy']
team_view ['hugo']
name test_sub2
name test_sub_sub
team_edit ['BusinessOperations', 'Freddy']
team_view ['hugo']

How to use a dictionary in recursion

Do you simply want to insert an item into a dictionary, recur, and then remove the item:

def algo(M, v):
    for u in v.neighbors:
        # do stuff
        M[u.name] = u  # temporarily extend dictionary
        result = algo(M, u)
        del M[u.name]  # clean up
        # check result

If you want to make sure the dictionary is pristine for the next iteration and recurance, you can pass an augmented (shallow) copy:

def algo(M, v):
    for u in v.neighbors:
        # do stuff
        # create a new extended dictionary on the fly
        result = algo({**M, u.name: u}, u))
        # no need to clean up afterwards
        # check result

If you're not running Python 3.5 or later, then use a more verbose syntax, something like:

def algo(M, v):
    for u in v.neighbors:
        # do stuff
        # create a new extended dictionary on the fly
        result = algo(dict(list(M.items()) + [(u.name, u)]), u))
        # no need to clean up afterwards
        # check result

Or are you trying to achieve something else?

Recursive function to return a dictionary in Python

Your code is almost correct. It has to be adjusted a little, though.
More specifically,

1. element is a file or directory name (not path). If it is a subdirectory or file in a subdirectory the value of if os.path.isfile(element) and elif os.path.isdir(element) will be always False. Hence, replace them with if os.path.isfile(os.path.join(root, element)) and elif os.path.isdir(os.path.join(root, element)) respectively.

2. Similarly, with open(element) should be replaced by with open(os.path.join(root,element)).

3. When reading the file's first line, you have to store the path and that line in a dictionary.

4. That dictionary has to be updated when calling the recursive function in elif os.path.isdir(element).

See below for the complete snippet:

import os

def search(root):

    my_dict = {}   # this is the final dictionary to be populated

    for element in os.listdir(root):
        
        if os.path.isfile(os.path.join(root, element)):
            try: 
                with open(os.path.join(root, element)) as file:
                    my_dict[os.path.join(root, element)] = file.readline() # populate the dictionary
            except UnicodeDecodeError: 
                # This exception handling has been put here to ignore decode errors (some files cannot be read)
                pass

        elif os.path.isdir(os.path.join(root, element)):
            my_dict.update(search(os.path.join(root,element)))  # update the current dictionary with the one resulting from the recursive call

    return my_dict

print(search('.'))

It prints a dictionary like below:

{
 "path/file.csv": "name,surname,grade",
 "path/to/file1.txt": "this is the first line of file 1",
 "path/to/file2.py": "import os"
}

For the sake of readability, os.path.join(root, element) can be stored in a variable, then:

import os

def search(root):

    my_dict = {}   # this is the final dictionary to be populated

    for element in os.listdir(root):
        path = os.path.join(root, element)

        if os.path.isfile(path):
            with open(path) as file:
                my_dict[path] = file.readline()

        elif os.path.isdir(path):
            my_dict.update(search(path))

    return my_dict

print(search('.'))

Finding a key recursively in a dictionary

when you recurse, you need to return the result of _finditem

def _finditem(obj, key):
    if key in obj: return obj[key]
    for k, v in obj.items():
        if isinstance(v,dict):
            return _finditem(v, key)  #added return statement

To fix the actual algorithm, you need to realize that _finditem returns None if it didn't find anything, so you need to check that explicitly to prevent an early return:

def _finditem(obj, key):
    if key in obj: return obj[key]
    for k, v in obj.items():
        if isinstance(v,dict):
            item = _finditem(v, key)
            if item is not None:
                return item

Of course, that will fail if you have None values in any of your dictionaries. In that case, you could set up a sentinel object() for this function and return that in the case that you don't find anything -- Then you can check against the sentinel to know if you found something or not.

Recursive function in nested dictionaries

For your particular case, I recommend using an explicit whitelist of allowed function names which map to functions in Python (see WHITELIST in the code below). This mitigates lots of potentially nasty security issues if you're trying to parse untrusted data. It also deals with your "none" requirement which doesn't map to a real function in Python.

The important part of the code is the parse function. It recursively walks through your input data and classifies every key as a function or a variable name. If it's a function, it calls that function with that key's value. Otherwise, it just uses the value. Either way, this info gets saved to results which gets recursively passed to the caller.

Note that this implementation doesn't even begin to attempt to deal with malformed input. I strongly recommend wrapping parse in a try ... catch block to gracefully deal with bad input.

data = {
    'any': {
        'none': {'value1': 0},
        'sum': {'value2': 0, 'value3': 1}
    }
}

# This can be expanded to include other functions that aren't built-in.
# Note that "none" is special because "not" isn't actually a function.
WHITELIST = {
    "any": any,
    "all": all,
    "sum": sum,
    "none": lambda x: not x
    "10": is_10 # Sample additional function you could add.
}

def is_10(values):
    return sum(values) == 10

def parse(data):
    results = []
    # Uncomment the next line if you're on Python 2.
    # for key, value in d.iteritems():
    # Leave this line if you're on Python 3.
    for key, value in data.items():
        if key in WHITELIST:
            # This is a function.
            function = WHITELIST[key]
            args = parse(value)
            results.append(function(args))
        else:
            # This is a value, so the name doesn't actually matter.
            results.append(value)
    return results

print(parse(data))

For the example at the top of the code, it prints[True] because their is a single function at the root of the data. If your data always has a single root function, you probably want to call parse as output = parse(data)[0].

---

Related Topics