def _flatten_dict(xs):
  """Flatten a nested dictionary.

  The nested keys are flattened to a tuple.

  Example::

    xs = {'foo': 1, 'bar': {'a': 2, 'b': {}}}
    flat_xs = flatten_dict(xs)
    print(flat_xs)
    # {
    #   ('foo',): 1,
    #   ('bar', 'a'): 2,
    # }

  Note that empty dictionaries are ignored and
  will not be restored by `unflatten_dict`.

  Args:
    xs: a nested dictionary

  Returns:
    The flattened dictionary.
  """
  assert isinstance(xs, dict), 'input is not a dict'

  def _flatten(xs, prefix):
    if not isinstance(xs, dict):
      return {prefix: xs}
    result = {}
    for key, value in xs.items():
      path = prefix + (key,)
      result.update(_flatten(value, path))
    return result

  return _flatten(xs, ())