Python Deeply Nested Dictionary of a Specific Type

Question

I would like to have a dictionary deeply nested. Lets consider that "deeply". To show what I would need a 5 level dictionary, e.g., foo[1][2][3][4][5] that would have a set or list as item.

As I saw here I could accomplish that in, at least, two ways:

from collections import defaultdict
foo = defaultdict(lambda: defaultdict(lambda:defaultdict(lambda: defaultdict(lambda: defaultdict(set)))))

or

from functools import partial
foo = defaultdict(partial(defaultdict, partial(defaultdict, partial(defaultdict, partial(defaultdict, set)))))

and then in both cases I could, for example, foo[1][2][3][4][5].add(1)

But I was looking for a less cumbersome way to accomplish this and found two approaches. The first one also provided in the same place as the aforementioned solutions:

class NestedDict(dict):
  def __getitem__(self, key):
    if key in self: return self.get(key)
    return self.setdefault(key, NestedDict())

and the second equivalent found here at SO as a answer to an Autovivification question.

class NestedDict(dict):
  """Implementation of perl's autovivification feature."""
  def __getitem__(self, item):
    try:
      print "__getitem__: %s" % item
      return dict.__getitem__(self, item)
    except KeyError:
      value = self[item] = type(self)()
      print "value: %s" % value
      return value

I liked those last two approaches, but I do not know how to change them in order to generate a nested dictionary of a specific type that is not dict, e.g., set or list as accomplished with defaultdict.

Thanks in advance for any suggestion, comments, or corrections.

Answer 1

Here is an autovivifier which does not require you to set the level at which you want the default factory. When you get an attribute that does not exist on the DefaultHasher, it changes itself into an instance of the default factory:

class DefaultHasher(dict):
    def __init__(self, default_factory, change_self=None):
        self.default_factory = default_factory
        self.change_self = change_self
    def change(self, key):
        def _change():
            x = self.default_factory()
            self[key] = x
            return x
        return _change
    def __missing__(self, key):
        self[key] = DefaultHasher(self.default_factory,
                                  self.change(key))
        return self[key]
    def __getattr__(self, name):
        result = self.change_self()
        return getattr(result, name)

foo = DefaultHasher(set)
foo[1][2][3][4][5].add(1)
print(foo)
# {1: {2: {3: {4: {5: set([1])}}}}}

foo[1][2][3].add(20)
print(foo)
# {1: {2: {3: set([20])}}}

foo[1][3] = foo[1][2]
print(foo)
# {1: {2: {3: set([20])}, 3: {3: set([20])}}}

foo[1][2].add(30)
print(foo)
# {1: {2: set([30]), 3: {3: set([20])}}}

Answer 2

This approach is similar to your first example, except you can specify whatever depth you want without a lot of typing.

from collections import defaultdict

def nested_default_dict(num_keys, init_func):
    if num_keys == 1:
        return defaultdict(init_func)
    else:
        return defaultdict(lambda: nested_default_dict(num_keys-1, init_func))

foo = nested_default_dict(5, set)
foo[1][2][3][4][5].add("Hello World")
foo[1][2][3][4][5].add("Lorem Ipsum")
foo[1][2][3][4][5].add("Dolor sit amet")
print foo[1][2][3][4][5]

bar = nested_default_dict(3, list)
bar[4][8][15].append(16)
bar[4][8][15].append(23)
bar[4][8][15].append(42)
print bar[4][8][15]

Result:

set(['Dolor sit amet', 'Lorem Ipsum', 'Hello World'])
[16, 23, 42]

One drawback is that the dicts don't look very pretty when you print them:

>>>print foo
defaultdict(<function <lambda> at 0x0000000001FA8A58>, {1: defaultdict(<function <lambda> at 0x0000000001FAB198>, {2: defaultdict(<function <lambda> at 0x0000000001FAB208>, {3: defaultdict(<function <lambda> at 0x0000000001FAB278>, {4: defaultdict(<type 'set'>, {5: set(['Dolor sit amet', 'Lorem Ipsum', 'Hello World'])})})})})})