def flatten(data):
    """ Flatten a nested dict into a sequence of (keypath, value).

        - `keypath` is a list giving the keys to get to the corresponding value
        - `value` is the value at this keypath - if this is a nested dict then it is shown as an empty dict {}
           with the nested values shown at their corresponding keypaths.
    """
    stack = [([], data)]
    results = []
    while stack:
        keyparts, data = stack.pop(0)
        if isinstance(data, dict):
            if keyparts != []:
                results.append((tuple(keyparts), {}))
            for k in sorted(data.keys()):
                stack.append((keyparts + [k], data[k]))
        else:
            results.append((tuple(keyparts), data))
    return results