Code problem - Flatten dictionary using generator

Question

First, this post is a solution not using generators: Flatten dictionary of dictionaries

I have a dictionary of dictionaries.

For example:

{
    "name": {
        "first": "One",
        "last": "Drone"
    },
    "job": "scout",
    "recent": {},
    "additional": {
        "place": {
            "zone": "1",
            "cell": "2"}
    }
}

The result will be:

{"name/first": "One",           #one parent
 "name/last": "Drone",
 "job": "scout",                #root key
 "recent": "",                  #empty dict
 "additional/place/zone": "1",  #third level
 "additional/place/cell": "2"}

I tried solving it differently and the keys just won't return if you could help me figuring how to use the recursion over there.. By the way this is an exercise from checkio.org

def flatten(a):
    arr = flatten_dictionary(a)
    newDict = {}
    for i in arr:
        temp = i.split(':')
        try:
            newDict[temp[0]]=temp[1]
        except:
            pass
    return newDict
def flatten_dictionary(a):
    for i in a:
        if isinstance(a[i],type(dict)):
            yield from(i+'/' + flatten(a[i])) #won't enter this if scope
        else:
            yield ':'+a[i]

Here are some asserts if you want to test it..

 assert flatten({"key": "value"}) == {"key": "value"}, "Simple"
 assert flatten(
    {"key": {"deeper": {"more": {"enough": "value"}}}}
) == {"key/deeper/more/enough": "value"}, "Nested"
assert flatten({"empty": {}}) == {"empty": ""}, "Empty value"
assert flatten({"name": {
                    "first": "One",
                    "last": "Drone"},
                "job": "scout",
                "recent": {},
                "additional": {
                    "place": {
                        "zone": "1",
                        "cell": "2"}}}
) == {"name/first": "One",
      "name/last": "Drone",
      "job": "scout",
      "recent": "",
      "additional/place/zone": "1",
      "additional/place/cell": "2"}

Also, right now this is my result: {"":"value"}

Well, first, the line `if isinstance(a[i],type(dict))` will check whether `a[i]` is a `type`, as `type(dict)` is `type`. You need `if isinstance(a[i],dict)`, but that alone does not fix it. — tobias_k, Oct 07 '19 at 09:26
`type()` is not needed for `isinstance`, and you probably don't need any string operations for this task. Use tuples/lists if you want to return multiple values. — Alex P., Oct 07 '19 at 09:27

tobias_k · Accepted Answer · 2019-10-07T09:46:11.923

The first problem is that with if isinstance(a[i],type(dict)) you are testing whether the item is an instance of type(dict), which is type, not dict, but that does not fix all the problems.

>>> type(dict)
<type 'type'>
>>> dict
<type 'dict'>

While you are asking for a solution using generators, I don't think that this really makes sense here, as you want to return a dictionary, and not just any iterable. Thus, you could only use the generator for an inner function (like you do), making the code unneccesarily complicated.

Instead, I'd suggest just using something like this, which passes all your asserts:

def flatten(d):
    res = {}
    for key, val in d.items():
        if isinstance(val, dict):
            if not val:
                res[key] = ""
            for k2, v2 in flatten(val).items():
                res["%s/%s" % (key, k2)] = v2
        else:
            res[key] = val
    return res

If you really want to keep that inner-generator-style, you can use this:

def flatten(d):
    return dict(_flatten_gen(d))

def _flatten_gen(d):
    for key, val in d.items():
        if isinstance(val, dict):
            if not val:
                yield (key, "")
            yield from (("%s/%s" % (key, k2), v2) for k2, v2 in flatten(val).items())
        else:
            yield (key, val)

Note that this is yielding tuples, which can be passed directly to the dict constructor, instead of joining and then splitting keys and values by :. (In fact, this way, it might actually make sense to have the generator, as you could just call _flatten_gen(d) instead of flatten(d).items() if you just want to iterate all the flattened items and do not need the dictionary itself.)

Besides the approach of keeping an inner function, which approach has a more effiecient complexity? — eladgl, Oct 07 '19 at 09:45
@eladgl It's not a question of complexity, that is the same for both, more a question of readability, which is a matter of taste. However, meanwhile I quite llike the inner-gen-approach, see my last sentence. But if you just want to create the dict, then the benefit of the generator -- being able to create one item at a time instead of all at once -- is not used. — tobias_k, Oct 07 '19 at 09:47

Code problem - Flatten dictionary using generator

1 Answers1