Search code examples
pythontriedefaultdict

Can someone explain def _trie(): return defaultdict(_trie)

Can someone explain def _trie(): return defaultdict(_trie) ?

I know defaultdict and it looks like a recursive function. But I have not figured out how function name can become a parameter to defaultdict.

BTW, I got this trie implementation from https://stackoverflow.com/a/49357789/301513

Solution

  • The argument for defaultdict is a function.

    Start by calling _trie:

    >>> d = _trie()
>>> d
defaultdict(<function _trie at 0x105a9e400>, {})

    You now have an instance of defaultdict. What happens if you try to access a non-existent key?

    >>> d[3]
defaultdict(<function _trie at 0x105a9e400>, {})

    You get back another defaultdict, because d[3] is short for d.__getitem__(3) invokes d.__missing__(3), which calls d.__setattr__(d, 3, _trie().

    It reflects the recursive definition of a trie: a trie is either empty or a single node with tries as children. This creates a defaultdict that is either empty, or has arbitrary keys mapped to other defaultdicts with the same factory function.

    It's a little bit like mutual recursion. A call to _trie results in a call to defaultdict, but a call to defaultdict.__getitem__ or defaultdict.__setitem__ (rather than a call to defaultdict itself) results in a call to _trie.