Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

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.

share|improve this question
add comment

2 Answers

up vote 2 down vote accepted

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)
share|improve this answer
    
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? –  Lim H. Jan 29 '13 at 16:39
    
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... –  Lim H. Jan 29 '13 at 16:45
    
@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. –  Winston Ewert Jan 29 '13 at 17:05
    
No, you did not return a flattened dict and merge it. You ignore the return value of your recursive function call. Your function modifies what is passed to it which is exactly that which you aren't supposed to do in functional style. –  Winston Ewert Jan 29 '13 at 17:07
2  
@JohnOptionalSmith, I see the problem in the second version, but the first seems to work for me... test case? –  Winston Ewert Jan 29 '13 at 21:36
show 5 more comments

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

Ok, now List isn't the best data structure to append items, but that's another story !

share|improve this answer
    
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? –  Lim H. Jan 30 '13 at 9:27
    
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. –  John Optional Smith Jan 30 '13 at 10:25
    
My bad : Winston's implementation with yield is ok ! –  John Optional Smith Jan 30 '13 at 10:34
    
Is packing multiple objectives in the same function bad? I.e., is it bad style or is it conceptually incorrect? –  Lim H. Jan 30 '13 at 11:38
    
@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). –  John Optional Smith Jan 30 '13 at 21:01
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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