By Corley Brigman


2013-10-04 19:28:50 8 Comments

Is there a way to make a defaultdict also be the default for the defaultdict? (i.e. infinite-level recursive defaultdict?)

I want to be able to do:

x = defaultdict(...stuff...)
x[0][1][0]
{}

So, I can do x = defaultdict(defaultdict), but that's only a second level:

x[0]
{}
x[0][0]
KeyError: 0

There are recipes that can do this. But can it be done simply just using the normal defaultdict arguments?

Note this is asking how to do an infinite-level recursive defaultdict, so it's distinct to Python: defaultdict of defaultdict?, which was how to do a two-level defaultdict.

I'll probably just end up using the bunch pattern, but when I realized I didn't know how to do this, it got me interested.

5 comments

@Стас Цепа 2019-05-28 09:12:50

I would also propose more OOP-styled implementation, which supports infinite nesting as well as properly formatted repr.

class NestedDefaultDict(defaultdict):
    def __init__(self):
        super(NestedDefaultDict, self).__init__(NestedDefaultDict)

    def __repr__(self):
        return repr(dict(self))

Usage:

my_dict = NestedDefaultDict()
my_dict['a']['b'] = 1
my_dict['a']['c']['d'] = 2
my_dict['b']

print(my_dict)  # {'a': {'b': 1, 'c': {'d': 2}}, 'b': {}}

@pts 2013-10-04 20:01:29

Similar to BrenBarn's solution, but doesn't contain the name of the variable tree twice, so it works even after changes to the variable dictionary:

tree = (lambda f: f(f))(lambda a: (lambda: defaultdict(a(a))))

Then you can create each new x with x = tree().


For the def version, we can use function closure scope to protect the data structure from the flaw where existing instances stop working if the tree name is rebound. It looks like this:

from collections import defaultdict

def tree():
    def the_tree():
        return defaultdict(the_tree)
    return the_tree()

@Corley Brigman 2013-10-04 20:58:56

i'll have to think about this one (it's a little more complex). but i think your point is that if do x = tree(), but then someone comes by later and does tree=None, this one would still work, and that would wouldn't?

@pts 2013-10-04 23:25:45

Correct, that's my point.

@Chris W. 2015-01-07 01:11:08

The other answers here tell you how to create a defaultdict which contains "infinitely many" defaultdict, but they fail to address what I think may have been your initial need which was to simply have a two-depth defaultdict.

You may have been looking for:

defaultdict(lambda: defaultdict(dict))

The reasons why you might prefer this construct are:

  • It is more explicit than the recursive solution, and therefore likely more understandable to the reader.
  • This enables the "leaf" of the defaultdict to be something other than a dictionary, e.g.,: defaultdict(lambda: defaultdict(list)) or defaultdict(lambda: defaultdict(set))

@Yuvaraj Loganathan 2015-02-09 10:12:27

defaultdict(lambda: defaultdict(list)) The correct form ?

@Chris W. 2015-02-12 20:39:30

Ooops, yes, the lambda form is correct--because the defaultdict(something) returns a dictionary-like object, but defaultdict expects a callable! Thank you!

@Corley Brigman 2017-01-13 19:52:26

This got marked as a possible duplicate of another question... but it wasn't my original question. I knew how to create a two-level defaultdict; what I didn't know was how to make it recursive. This answer is, in fact, similar to stackoverflow.com/questions/5029934/…

@BrenBarn 2013-10-04 19:34:18

There is a nifty trick for doing that:

tree = lambda: defaultdict(tree)

Then you can create your x with x = tree().

@StackG 2018-11-16 05:52:13

This is AWESOME!

@Andrew Clark 2013-10-04 19:33:55

For an arbitrary number of levels:

def rec_dd():
    return defaultdict(rec_dd)

>>> x = rec_dd()
>>> x['a']['b']['c']['d']
defaultdict(<function rec_dd at 0x7f0dcef81500>, {})
>>> print json.dumps(x)
{"a": {"b": {"c": {"d": {}}}}}

Of course you could also do this with a lambda, but I find lambdas to be less readable. In any case it would look like this:

rec_dd = lambda: defaultdict(rec_dd)

@David Belohrad 2017-03-04 20:52:36

Indeed a perfect example, thanks. Could you please extend it to the case, that the data are loaded from json into defaultdict of defaultdict?

@Viacheslav Kondratiuk 2017-04-03 11:52:27

One note. If you are trying to use this code while pickling lambda won't work.

Related Questions

Sponsored Content

26 Answered Questions

[SOLVED] How can I safely create a nested directory?

21 Answered Questions

[SOLVED] How can I access and process nested objects, arrays or JSON?

5 Answered Questions

[SOLVED] Python: defaultdict of defaultdict?

  • 2011-02-17 14:04:22
  • Jonathan
  • 65717 View
  • 267 Score
  • 5 Answer
  • Tags:   python collections

22 Answered Questions

[SOLVED] Peak detection in a 2D array

3 Answered Questions

[SOLVED] Python: convert defaultdict to dict

  • 2013-12-06 16:17:32
  • user2988464
  • 33305 View
  • 65 Score
  • 3 Answer
  • Tags:   python defaultdict

2 Answered Questions

1 Answered Questions

[SOLVED] How to change defaultdict to normal dict

2 Answered Questions

36 Answered Questions

[SOLVED] What does Ruby have that Python doesn't, and vice versa?

  • 2009-07-11 12:24:26
  • Lennart Regebro
  • 123696 View
  • 264 Score
  • 36 Answer
  • Tags:   python ruby

3 Answered Questions

[SOLVED] Python: How to create nested XML from a flat datastructure

Sponsored Content