class getting kwargs from enclosing scope

Question

Python seems to be inferring some kwargs from the enclosing scope of a class method, and I'm not sure why. I'm implementing a Trie:

class TrieNode(object):
  def __init__(self, value = None, children = {}):
    self.children = children
    self.value = value

  def __getitem__(self, key):
    if key == "":
        return self.value
    return self.children[key[0]].__getitem__(key[1:])

  def __setitem__(self, key, value):
    if key == "":
        self.value = value
        return
    if key[0] not in self.children:
        self.children[key[0]] = TrieNode()
    self.children[key[0]].__setitem__(key[1:], value)

On the second to last line, I create a new TrieNode with, presumably, an empty dictionary of children. However, when I inspect the resulting data structure, all of the TrieNodes in the tree are, using the same children dictionary. Viz, if we do:

>>>test = TrieNode()
>>>test["pickle"] = 5
>>>test.children.keys()
['c', 'e', 'i', 'k', 'l', 'p']

Whereas the children of test should only consist of "p" pointing to a new TrieNode. On the other hand, if we go into the second to last line of that code and replace it with:

        self.children[key[0]] = TrieNode(children = {})

Then it works as expected. Somehow, then, the self.children dictionary is getting passed implicitly as a kwarg to TrieNode(), but why?

Answer 1

You're having a mutable default argument issue. Change your __init__ function to be like this

def __init__(self, value=None, children=None):
    if not children:
        children = {}

The default value for children will only be evaluated once at the point of function creation, whereas you want it to be a new dict at within each call.

Here's a simple example of the problem using a list

>>> def f(seq=[]):
...     seq.append('x') #append one 'x' to the argument
...     print(seq) # print it
>>> f() # as expected
['x']
>>> f() # but this appends 'x' to the same list
['x', 'x']
>>> f() # again it grows
['x', 'x', 'x']
>>> f()
['x', 'x', 'x', 'x']
>>> f()
['x', 'x', 'x', 'x', 'x']

As the the answer I linked to describes, this bites every python programmer eventually.