Flatten dictionary in Python (functional style)

Question

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.

Answer 1

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)

Answer 2

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) }