13
\$\begingroup\$

I'm trying to learn how to write functional code with Python and have found some tutorials online. Please note that I know Python is not a promoter for functional programming. I just want to try it out. One tutorial in particular gives this as an exercise:

Write a function flatten_dict to flatten a nested dictionary by joining the keys with . character.

So I decided to give it a try. Here is what I have and it works fine:

def flatten_dict(d, result={}, prv_keys=[]):

    for k, v in d.iteritems():
        if isinstance(v, dict):
            flatten_dict(v, result, prv_keys + [k])
        else:
            result['.'.join(prv_keys + [k])] = v

return result

I'd like to know whether this is the best way to solve the problem in python. In particular, I really don't like to pass a list of previous keys to the recursive call.

\$\endgroup\$
17
\$\begingroup\$

Your solution really isn't at all functional. You should return a flattened dict and then merge that into your current dictionary. You should also not modify the dictionary, instead create it with all the values it should have. Here is my approach:

def flatten_dict(d):
    def items():
        for key, value in d.items():
            if isinstance(value, dict):
                for subkey, subvalue in flatten_dict(value).items():
                    yield key + "." + subkey, subvalue
            else:
                yield key, value

    return dict(items())

Alternative which avoids yield

def flatten_dict(d):
    def expand(key, value):
        if isinstance(value, dict):
            return [ (key + '.' + k, v) for k, v in flatten_dict(value).items() ]
        else:
            return [ (key, value) ]

    items = [ item for k, v in d.items() for item in expand(k, v) ]

    return dict(items)
\$\endgroup\$
  • \$\begingroup\$ Thanks. I was trying to iterate through the result during each recursive step but it returns an error stating the size of the dictionary changed. I'm new to python and I barely understand yield. Is it because yield creates the value on the fly without storing them that the code is not blocked anymore? \$\endgroup\$ – Lim H. Jan 29 '13 at 16:39
  • \$\begingroup\$ One thing though. I did return a flattened dict and merged it into a current dictionary, which is the flattened result of the original dictionary. I'd like to know why it was not functional at all... \$\endgroup\$ – Lim H. Jan 29 '13 at 16:45
  • \$\begingroup\$ @LimH., if you got that error you were modifying the dictionary you were iterating over. If you are trying to be functional, you shouldn't be modifying dictionaries at all. \$\endgroup\$ – Winston Ewert Jan 29 '13 at 17:05
  • 2
    \$\begingroup\$ @JohnOptionalSmith, I see the problem in the second version, but the first seems to work for me... test case? \$\endgroup\$ – Winston Ewert Jan 29 '13 at 21:36
  • 2
    \$\begingroup\$ @zelusp, the benefit is organizational, the function inside the function is part of of the implementation of the outer function, and putting the function inside makes it clear and prevents other functions from using it. \$\endgroup\$ – Winston Ewert Oct 24 '16 at 21:20
8
\$\begingroup\$

Beside avoiding mutations, functional mindset demands to split into elementary functions, along two axes:

  1. Decouple responsibilities.
  2. By case analysis (eg pattern matching). Here scalar vs dict.

Regarding 1, nested dict traversal has nothing to do with the requirement to create dot separated keys. We've better return a list a keys, and concatenate them afterward. Thus, if you change your mind (using another separator, making abbreviations...), you don't have to dive in the iterator code -and worse, modify it.

def iteritems_nested(d):
  def fetch (suffixes, v0) :
    if isinstance(v0, dict):
      for k, v in v0.items() :
        for i in fetch(suffixes + [k], v):  # "yield from" in python3.3
          yield i
    else:
      yield (suffixes, v0)

  return fetch([], d)

def flatten_dict(d) :
  return dict( ('.'.join(ks), v) for ks, v in iteritems_nested(d))
  #return { '.'.join(ks) : v for ks,v in iteritems_nested(d) }
\$\endgroup\$
  • \$\begingroup\$ Thank you for your response. Let me see if I get this right. Basically there are two strategies here. One is to recursively construct the dictionary result and one is to construct the suffixes. I used the second approach but my mistake was that I passed a reference of the result down the recursive chains but the key part is correct. Is that right? Winston Etwert used the first approach right? What's wrong with his code? \$\endgroup\$ – Lim H. Jan 30 '13 at 9:27
  • \$\begingroup\$ The point is to (a) collect keys until deepest level and (b) concatenate them. You indeed did separate the two (although packed in the same function). Winston concatenate on the fly without modifying (mutating) anything, but an issue lies in recursion. \$\endgroup\$ – YvesgereY Jan 30 '13 at 10:25
  • \$\begingroup\$ My bad : Winston's implementation with yield is ok ! \$\endgroup\$ – YvesgereY Jan 30 '13 at 10:34
  • \$\begingroup\$ Is packing multiple objectives in the same function bad? I.e., is it bad style or is it conceptually incorrect? \$\endgroup\$ – Lim H. Jan 30 '13 at 11:38
  • \$\begingroup\$ @LimH. Both !. It can be necessary for performance reason, since Python won't neither inline nor defer computation (lazy programming). To alleviate this point, you can follow the opposite approach : provide to the iterator the way to collect keys -via a folding function- (strategy pattern, kind of). \$\endgroup\$ – YvesgereY Jan 30 '13 at 21:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.