Walk recursively through dictionaries and return result without using global variable

Question

I need to walk through several nested dictionaries in a recursive way and return a value of the type property.

How my code could be improved? Especially, how to do it without a global variable?

field_mapping = { 
  "logic_index" : {
    "mappings" : {
      "Patient" : {
        "Diagnosis.Diagnosis_Start_Date" : {
          "full_name" : "Diagnosis.Diagnosis_Start_Date",
          "mapping" : {
            "Diagnosis_Start_Date" : {
              "type" : "date",
              "format" : "strict_date_optional_time||epoch_millis"
            }
          }
        }
      }
    }
  }
}

def get_field_type(mapping):
    ftype = 'string' 

    def parse_mapping(mapping):
        global ftype
        for key, item in mapping.iteritems():
            if isinstance(item, dict):
                parse_mapping(item)
            elif key == 'type': 
                ftype = item
        return ftype

    ftype = parse_mapping(mapping)
    return ftype

ftype = get_field_type(field_mapping)
print(ftype)

Answer 1

1. Review

1. There's no docstring, and so it's not clear exactly what this function is intended to compute. In particular, it's not clear what you want to get in these cases:

   (a) if there are no items in the data structure with the key "type"?

   (b) if there are multiple items in the data structure with the key "type"?

   The code you posted raises an exception in case (a):

   NameError: name 'ftype' is not defined
   

   and in case (b) it returns the value of the last visited item with that key (which could be any item, since dictionaries may be iterated over in any order).

   I'm going to assume that in case (a) you'd actually like to get the default value 'string', and that in case (b) you don't care which value you get and any item with the right key is fine.

2. The values 'type' and 'string' seem arbitrary, and so it would make sense for them to be parameters to the function.

2. Non-local exit

The problem here is to implement a non-local exit — that is, when you find the value you're after, you want to return all the way up the call stack to the original caller, bypassing all the intermediate calls. This is a job for an exception.

def get_field_type(mapping, key='type', default='string'):
    """Return a value corresponding to the specified key in the (possibly
    nested) mapping. If there is no item with that key, return
    default.

    """
    class Found(Exception):
        pass
    def search(mapping):
        for k, v in mapping.iteritems():
            if isinstance(v, dict):
                search(v)
            elif k == key:
                raise Found(v)
    try:
        search(mapping)
    except Found as exc:
        return exc.args[0]
    else:
        return default

3. Stack of iterators

Alternatively, you could avoid using recursion and instead maintain the current search state using a stack of iterators. Then there's no difficulty: when you find the item you want you can return it immediately.

def get_field_type(mapping, key='type', default='string'):
    """Return a value corresponding to the specified key in the (possibly
    nested) mapping. If there is no item with that key, return
    default.

    """
    stack = [mapping.iteritems()]
    while stack:
        for k, v in stack[-1]:
            if isinstance(v, dict):
                stack.append(v.iteritems())
                break
            elif k == key:
                return v
        else:
            stack.pop()
    return default

(In Python 3 you need to write iter(mapping.items()) instead of mapping.iteritems() and similarly iter(v.items()) instead of v.iteritems().)