Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

One-line Tree In Python

gist.github.com

Post reply on HN
Print view View original

31–38 of 38 posts

Re: One-line Tree In Python

#31

Post by krosaen »

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

Re: One-line Tree In Python

#32

Post by mikeash »

abecedarius wrote: post #29
mikeash wrote: post #23

Earlier quoted context omitted.

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 '…

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.

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.

Re: One-line Tree In Python

#33

Post by scott_s »

ajross wrote: post #19
rauljara wrote: post #9

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 Btw. How do you post nicely formatted code? edit - Thanks!

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 > does what you expect when you try: my_map[12][3] = some_value;

I was so used to the semantics of std::map that I was surprised it didn't work that way in Python.

Re: One-line Tree In Python

#34

Post by ajross »

scott_s wrote: post #33
ajross wrote: post #19

Earlier quoted context omitted.

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 > does what you expect when you try: my_map[12][3] = some_value;

I was so used to the semantics of std::map that I was surprised it didn't work that way in Python.

Autovivification through a rvalue (for clarity: the magic here is that x[a][b]=c works to create x[a] despite that index never seeing an assignment) has a long history in perl. The C++ feature is more limited in scope and AFAIK accidental -- it works because the automatic construction is a side effect of reading the value, which is often considered an undesired feature of STL (you can't use an expression that contains x[a] to test if x contains a, like you can in many languages).

And you may be less cynical, but I've had to explain this sort of thing to a huge number of C++ programmers, most of whom write STL code that looks like Java, with explicit initialization of all the intermediate containers.

Re: One-line Tree In Python

#35

Post by bryanh »

joshu wrote: post #22
bryanh wrote: post #5

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 +=.

Also check out collections.Counter. x = collections.defaultdict(collections.Counter) x['foo']['bar'] += 1 X['foo'].most_common(10) Etc.

Excellent! I didn't know about that one!

Re: One-line Tree In Python

#36

Post by scooty-puff »

kd0amg wrote: post #17

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)]

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))

Re: One-line Tree In Python

#37

Post by scott_s »

ajross wrote: post #34
scott_s wrote: post #33

Earlier quoted context omitted.

I was so used to the semantics of std::map that I was surprised it didn't work that way in Python.

Autovivification through a rvalue (for clarity: the magic here is that x[a][b]=c works to create x[a] despite that index never seeing an assignment) has a long history in perl. The C++ feature is more limited in scope and AFAIK accidental -- it works because the automatic construction is a side effect of reading the value, which is often considered an undesired feature of STL (you can't use an expression that contain…

Automatic construction is not really a "side-effect" of reading a value in std::map, it's an explicit design choice. They want users to be able to write code like this:

  std::map dict;
  dict["one"] = 1;
  dict["two"] = 2;
  dict["three"] = 3;
If using operator[] on a key did not implicitly mean "create an entry for this key if it is not there," the above would not work. Rather, you would have to write the above as:

  std::map dict;
  dict.insert(std::make_pair("one", 1));
  dict.insert(std::make_pair("two", 2));
  dict.insert(std::make_pair("three", 3));
The reason being that std::map is purely a library, not a part of the language. It does not "know" that operator[] is actually being used as a part of an assignment.

Re: One-line Tree In Python

#38

Post by kragen »

scott_s wrote: post #37
ajross wrote: post #34

Earlier quoted context omitted.

Autovivification through a rvalue (for clarity: the magic here is that x[a][b]=c works to create x[a] despite that index never seeing an assignment) has a long history in perl. The C++ feature is more limited in scope and AFAIK accidental -- it works because the automatic construction is a side effect of reading the value, which is often considered an undesired feature of STL (you can't use an expression that contain…

Automatic construction is not really a "side-effect" of reading a value in std::map, it's an explicit design choice. They want users to be able to write code like this: std::map dict; dict["one"] = 1; dict["two"] = 2; dict["three"] = 3; If using operator[] on a key did not implicitly mean "create an entry for this key if it is not there," the above would not work. Rather, you would have to write the above as: std::ma…

Strictly speaking, it's a side effect, because it mutates an existing object. It's also a surprising and bug-prone side effect (as mentioned upthread; also, Darius Bacon found a bug or two in Norvig's spell-corrector due to the corresponding behavior of defaultdict in Python) and an avoidable side effect, although it's not avoidable in C++. In Ruby, Python, Smalltalk, Common Lisp, Lua, and many other languages, you can make this (or its weird-syntax equivalent) work:

    dict["one"] = 1;
without causing this to add "one" to the dictionary:

    if (dict["one"]) { /* ... */ }
even for a "dict" that is purely a library, not a part of the language.

The underlying problem is that C++ calls the same operator[] in both lvalue and rvalue contexts. Which is pretty odd, really, when you think about it; it certainly doesn't generate the same code for indexing into native arrays in lvalue and rvalue contexts. All the other languages distinguish between the lvalue and rvalue contexts. Ruby calls [] or []=, Python calls __getitem__ or __setitem__; Smalltalk has #at: and #at:put:; Common Lisp doesn't have separate names for the two things, but one of them is defined with (defun foo (dict key) ...) and the other is defined with (defun (setf foo) (dict key) ...); in Lua, these are the metamethods __index and __newindex.

So it's sort of true that it's not std::map's fault, but C++'s. But not really. Stroustrup fixed several things about the way templates worked to make STL work better; he should have fixed this one too.

Post reply on HN