6 ms·

One-line Tree In Python

277 points by kilovoltaire 15y ago

rollypolly 15y ago
Jebus that was simple! I wish I'd thought of it.
zbuc 15y ago
In Perl, this is called autovivification: https://en.wikipedia.org/wiki/Autovivification https://en.wikipedia.org/wiki/Autovivification I've wanted something like that in Python at different times... thanks! edit: Ha! The Wiki article even has basically the same code: def hash(): return defaultdict(hash)
- kilovoltaire 15y ago
  wow thanks i was actually really curious if there was a name for this sort of thing! added a note about it to the gist. i wonder whether it will be made part of more languages as JSON-esque nested objects proliferate in our code and minds.
- irahul 15y ago
  > I've wanted something like that in Python at different times... thanks! Python's auto-vivification doens't allow Perl's hap hazard auto-vivification. Perl allows you to say: my $foo = {}; $foo->{'blah'}[0]->{'bar'}++; And after this statement, $foo will refer a hash which has the structure as accessed in the statement. I don't think this can be done for a generalized case in Python. Whether I want is a totally different question.
  - jrockway 15y ago
    Why is this haphazard? If you don't want reads to change your data structure shape in a well-defined manner, use 'exists' or make an immutable hash with Hash::Util.
- tathagatadg 14y ago
  I always use http://stackoverflow.com/a/651879/276569 http://stackoverflow.com/a/651879/276569
afhof 15y ago
I would be interest to see this using the __getattr__ rather than __getitem__, so that this is also possible: users = tree() users.harold.username = 'hrldcpr' users.handler.username = 'matthandlersux'
- albertzeyer 15y ago
  Well, it's as trivial as you say. Just set __getattr__ = __getitem__ in your tree. (Note though that there is/was a small bug(?) in CPython: http://bugs.python.org/issue14658 http://bugs.python.org/issue14658)
  - afhof 15y ago
    Seems like it may take a little more than one line, this errors for me: >>> a = tree() >>> a.__getattr__ = a.__getitem__
    - albertzeyer 15y ago
      Yea, sure it becomes more than one line (or at least I don't know a good one-line-way) but I wouldn't count that as an issue. It errors for you because it is a defaultdict instance and doesn't allow attribute overwrites. This should work: class tree(defaultdict): def __init__(self): defaultdict.__init__(self, tree) __getattr__ = defaultdict.__getitem__ __setattr__ = defaultdict.__setitem__ Edit: It doesn't work with the simple assignment because of the mentioned bug. Ofc the fix is trivial. See the code from beagle3.
- beagle3 15y ago
  class attrdict(defaultdict): def __getattr__(self, key): return self[key] def __setattr__(self, key, val): self[key]=val def tree(): return attrdict(tree) attrdict is indeed a useful thing to have around. I usually base it off on the built in "dict", but as this example shows, it is useful on top of "defaultdict" as well.
bryanh 15y ago
This is actually quite elegant and useful. I've done similar things time and time again with code like so: defaultdict(lambda: defaultdict(int)) That allows me to organically build dictionaries (mainly for stat building) using operands like +=.
- joshu 15y ago
  Also check out collections.Counter. x = collections.defaultdict(collections.Counter) x['foo']['bar'] += 1 X['foo'].most_common(10) Etc.
  - bryanh 14y ago
    Excellent! I didn't know about that one!
rauljara 15y ago
Neat. Works in Ruby, too. def tree; Hash.new {|h, k| h[k] = tree }; end t = tree t[:foo][:bar] = "foobar" # => {:foo=>{:bar=>"foobar"}} Probably more idiomatic to do it as a class, though. class Tree < Hash def initialize super {|h,k| h[k] = Tree.new } end end Btw. How do you post nicely formatted code? edit - Thanks!
- anonymoushn 15y ago
  http://news.ycombinator.com/formatdoc http://news.ycombinator.com/formatdoc
- kilovoltaire 15y ago
  Nice. My friend made a fork along those lines as well: https://gist.github.com/2012439 https://gist.github.com/2012439 As for code in comments, see: http://news.ycombinator.com/formatdoc http://news.ycombinator.com/formatdoc
- jluxenberg 15y ago
  You can use the Y combinator to do this as well, without having to create a class or a top-level method: http://www.eecs.harvard.edu/~cduan/technical/ruby/ycombinator.shtml http://www.eecs.harvard.edu/~cduan/technical/ruby/ycombinato...
- ajross 15y ago
  It works in Ruby because it works in Perl. :) A little known fact is that it works in C++ STL too as long as the objects in your containers have default constructors that make sense. So a map<int, map<int, value_type> > does what you expect when you try: my_map[12][3] = some_value;
  - archangel_one 14y ago
    I don't think it's a little known fact that std::map works that way, ie. that operator [] inserts if the key doesn't exist (or at least, it's surely not little known among people using C++?). Also, I don't think you can have an infinitely expanding std::map in the same way, because all the key/value types have to get rolled into the type signature of the top level map. It's not that hard to write something yourself to achieve it, but it's not going to be the one-liner that it is in Python.
anonymoushn 15y ago
This is pretty good. I prefer the name I used when I needed it, though. dicts_all_the_way_down = lambda:defaultdict(dicts_all_the_way_down)
groovy2shoes 15y ago
A quick Lua version: do local mt = { __index = function(t, k) t[k] = tree() return t[k] end } function tree() return setmetatable({}, mt) end end t = tree() t.foo.bar = 'foobar'
kd0amg 15y ago
If only Haskell would let me do type MTree t = Map t (MTree t) This version works though. data Tree t = Leaf | Node [(t, Tree t)]
- scooty-puff 14y ago
  The problem is that the type would be expanded indefinitely: Map t (Map t (Map t ... Try: newtype MTree t = MTree (Map t (MTree t))
wicknicks 15y ago
This is a tree with labelled edges, not just a tree. This tree will not hold multiple values with the same label. I always imagine my trees to have no labelled edges. Very cool though!
abecedarius 15y ago
Very nice! I've been a bit leery though of defaultdict since it contributed to two different bugs in http://norvig.com/spell-correct.html http://norvig.com/spell-correct.html -- in less than a page of code, by a first-rate programmer, which was read by many thousands of others for years before anyone noticed the second bug. I'm not saying don't use this, I just have a little warning light blink on when I see 'defaultdict' anywhere.
- mikeash 15y ago
  Both of those errors seem like fundamental category errors. He's using a dictionary construct which effectively makes it so that every key has a value, but then relies on dictionary membership when testing. This happens to work, but it makes little sense. (One could argue that 'foo in bar' should always be True if bar is a defaultdict.) Seems to me like he should have checked the value of the word rather than using 'in'. You make a good point about this being written by a known intelligent person and seen by many others who didn't see the bugs, but I think it's ultimately a lesson in thinking about semantics rather than behavior. This code relies too much on the behavior of defaultdict rather than just what such a thing means. As long as what it means is kept in mind I think it should be safe. But that's just, like, my opinion, man.
  - abecedarius 14y ago
    At some level it was sloppy thinking, yes; most bugs have some obvious-in-retrospect reason they were stupid. You may be right about how to think about this one. I've seen other defaultdict bugs -- this is just the case with the highest eyeball-count-times-attention product I can point to.
    - mikeash 14y ago
      If this bug was simply due to having the wrong concept of defaultdict, and if the others you saw were the same, then you can avoid the bugs forever by just having the right concept. Lots of ifs there, of course.
raymondh 15y ago
+1 This is a beautiful little recipe.
deleted 14y ago
[deleted]
krosaen 14y ago
related, but not as clever function to help with nested counters (with doctest showing usage): def incr_nestedctr(d, *keys, **kwargs): """ >>> a = {} >>> incr_nestedctr(a, 'a', 'b', 'c', 'd') {'a': {'b': {'c': {'d': 1}}}} >>> incr_nestedctr(a, 'a', 'b', 'c', 'd') {'a': {'b': {'c': {'d': 2}}}} >>> incr_nestedctr(a, 'a', 'b', 'c', 'd', delta = -4) {'a': {'b': {'c': {'d': -2}}}} >>> incr_nestedctr({u'1.0': {u'0': 1, '5': 1}}, '1.0', '5', delta = 2) {u'1.0': {u'0': 1, '5': 3}} """ delta = kwargs.get('delta', 1) thed = d for k in keys[:-1]: thed = thed.setdefault(k, {}) thed.setdefault(keys[-1], 0) thed[keys[-1]] += delta return d

277 points by kilovoltaire 15y ago

Jebus that was simple! I wish I'd thought of it.

zbuc 15y ago

In Perl, this is called autovivification: https://en.wikipedia.org/wiki/Autovivification https://en.wikipedia.org/wiki/Autovivification I've wanted something like that in Python at different times... thanks! edit: Ha! The Wiki article even has basically the same code: def hash(): return defaultdict(hash)

kilovoltaire 15y ago
wow thanks i was actually really curious if there was a name for this sort of thing! added a note about it to the gist. i wonder whether it will be made part of more languages as JSON-esque nested objects proliferate in our code and minds.
irahul 15y ago
> I've wanted something like that in Python at different times... thanks! Python's auto-vivification doens't allow Perl's hap hazard auto-vivification. Perl allows you to say: my $foo = {}; $foo->{'blah'}[0]->{'bar'}++; And after this statement, $foo will refer a hash which has the structure as accessed in the statement. I don't think this can be done for a generalized case in Python. Whether I want is a totally different question.
- jrockway 15y ago
  Why is this haphazard? If you don't want reads to change your data structure shape in a well-defined manner, use 'exists' or make an immutable hash with Hash::Util.
tathagatadg 14y ago
I always use http://stackoverflow.com/a/651879/276569 http://stackoverflow.com/a/651879/276569

afhof 15y ago

I would be interest to see this using the __getattr__ rather than __getitem__, so that this is also possible: users = tree() users.harold.username = 'hrldcpr' users.handler.username = 'matthandlersux'

albertzeyer 15y ago
Well, it's as trivial as you say. Just set __getattr__ = __getitem__ in your tree. (Note though that there is/was a small bug(?) in CPython: http://bugs.python.org/issue14658 http://bugs.python.org/issue14658)
- afhof 15y ago
  Seems like it may take a little more than one line, this errors for me: >>> a = tree() >>> a.__getattr__ = a.__getitem__
  - albertzeyer 15y ago
    Yea, sure it becomes more than one line (or at least I don't know a good one-line-way) but I wouldn't count that as an issue. It errors for you because it is a defaultdict instance and doesn't allow attribute overwrites. This should work: class tree(defaultdict): def __init__(self): defaultdict.__init__(self, tree) __getattr__ = defaultdict.__getitem__ __setattr__ = defaultdict.__setitem__ Edit: It doesn't work with the simple assignment because of the mentioned bug. Ofc the fix is trivial. See the code from beagle3.
beagle3 15y ago
class attrdict(defaultdict): def __getattr__(self, key): return self[key] def __setattr__(self, key, val): self[key]=val def tree(): return attrdict(tree) attrdict is indeed a useful thing to have around. I usually base it off on the built in "dict", but as this example shows, it is useful on top of "defaultdict" as well.

bryanh 15y ago

This is actually quite elegant and useful. I've done similar things time and time again with code like so: defaultdict(lambda: defaultdict(int)) That allows me to organically build dictionaries (mainly for stat building) using operands like +=.

joshu 15y ago
Also check out collections.Counter. x = collections.defaultdict(collections.Counter) x['foo']['bar'] += 1 X['foo'].most_common(10) Etc.
- bryanh 14y ago
  Excellent! I didn't know about that one!

rauljara 15y ago

Neat. Works in Ruby, too. def tree; Hash.new {|h, k| h[k] = tree }; end t = tree t[:foo][:bar] = "foobar" # => {:foo=>{:bar=>"foobar"}} Probably more idiomatic to do it as a class, though. class Tree < Hash def initialize super {|h,k| h[k] = Tree.new } end end Btw. How do you post nicely formatted code? edit - Thanks!

anonymoushn 15y ago
http://news.ycombinator.com/formatdoc http://news.ycombinator.com/formatdoc
kilovoltaire 15y ago
Nice. My friend made a fork along those lines as well: https://gist.github.com/2012439 https://gist.github.com/2012439 As for code in comments, see: http://news.ycombinator.com/formatdoc http://news.ycombinator.com/formatdoc
jluxenberg 15y ago
You can use the Y combinator to do this as well, without having to create a class or a top-level method: http://www.eecs.harvard.edu/~cduan/technical/ruby/ycombinator.shtml http://www.eecs.harvard.edu/~cduan/technical/ruby/ycombinato...
ajross 15y ago
It works in Ruby because it works in Perl. :) A little known fact is that it works in C++ STL too as long as the objects in your containers have default constructors that make sense. So a map<int, map<int, value_type> > does what you expect when you try: my_map[12][3] = some_value;
- archangel_one 14y ago
  I don't think it's a little known fact that std::map works that way, ie. that operator [] inserts if the key doesn't exist (or at least, it's surely not little known among people using C++?). Also, I don't think you can have an infinitely expanding std::map in the same way, because all the key/value types have to get rolled into the type signature of the top level map. It's not that hard to write something yourself to achieve it, but it's not going to be the one-liner that it is in Python.

anonymoushn 15y ago

This is pretty good. I prefer the name I used when I needed it, though. dicts_all_the_way_down = lambda:defaultdict(dicts_all_the_way_down)

groovy2shoes 15y ago

A quick Lua version: do local mt = { __index = function(t, k) t[k] = tree() return t[k] end } function tree() return setmetatable({}, mt) end end t = tree() t.foo.bar = 'foobar'

kd0amg 15y ago

If only Haskell would let me do type MTree t = Map t (MTree t) This version works though. data Tree t = Leaf | Node [(t, Tree t)]

scooty-puff 14y ago
The problem is that the type would be expanded indefinitely: Map t (Map t (Map t ... Try: newtype MTree t = MTree (Map t (MTree t))

wicknicks 15y ago

This is a tree with labelled edges, not just a tree. This tree will not hold multiple values with the same label. I always imagine my trees to have no labelled edges. Very cool though!

abecedarius 15y ago

Very nice! I've been a bit leery though of defaultdict since it contributed to two different bugs in http://norvig.com/spell-correct.html http://norvig.com/spell-correct.html -- in less than a page of code, by a first-rate programmer, which was read by many thousands of others for years before anyone noticed the second bug. I'm not saying don't use this, I just have a little warning light blink on when I see 'defaultdict' anywhere.

mikeash 15y ago
Both of those errors seem like fundamental category errors. He's using a dictionary construct which effectively makes it so that every key has a value, but then relies on dictionary membership when testing. This happens to work, but it makes little sense. (One could argue that 'foo in bar' should always be True if bar is a defaultdict.) Seems to me like he should have checked the value of the word rather than using 'in'. You make a good point about this being written by a known intelligent person and seen by many others who didn't see the bugs, but I think it's ultimately a lesson in thinking about semantics rather than behavior. This code relies too much on the behavior of defaultdict rather than just what such a thing means. As long as what it means is kept in mind I think it should be safe. But that's just, like, my opinion, man.
- abecedarius 14y ago
  At some level it was sloppy thinking, yes; most bugs have some obvious-in-retrospect reason they were stupid. You may be right about how to think about this one. I've seen other defaultdict bugs -- this is just the case with the highest eyeball-count-times-attention product I can point to.
  - mikeash 14y ago
    If this bug was simply due to having the wrong concept of defaultdict, and if the others you saw were the same, then you can avoid the bugs forever by just having the right concept. Lots of ifs there, of course.

raymondh 15y ago

+1 This is a beautiful little recipe.

deleted 14y ago

[deleted]

krosaen 14y ago

related, but not as clever function to help with nested counters (with doctest showing usage): def incr_nestedctr(d, *keys, **kwargs): """ >>> a = {} >>> incr_nestedctr(a, 'a', 'b', 'c', 'd') {'a': {'b': {'c': {'d': 1}}}} >>> incr_nestedctr(a, 'a', 'b', 'c', 'd') {'a': {'b': {'c': {'d': 2}}}} >>> incr_nestedctr(a, 'a', 'b', 'c', 'd', delta = -4) {'a': {'b': {'c': {'d': -2}}}} >>> incr_nestedctr({u'1.0': {u'0': 1, '5': 1}}, '1.0', '5', delta = 2) {u'1.0': {u'0': 1, '5': 3}} """ delta = kwargs.get('delta', 1) thed = d for k in keys[:-1]: thed = thed.setdefault(k, {}) thed.setdefault(keys[-1], 0) thed[keys[-1]] += delta return d