[Tutor] Python creating trie

[Peter Otten]

anish singh wrote:

> Can someone explain me this code to create a trie
> from words?
> 
> import collections
> words = ["bad", "sad", "abyss"]
> 
> Trie = lambda: collections.defaultdict(Trie)
> trie = Trie()
> END = True
> 
> for i, word in enumerate(words):
>     reduce(dict.__getitem__, word, trie)[END] = i
> print(trie.values())
> 
> 
> I am not able to understand lambda usage and reduce
> function here.

foo = lambda: expr

is just another way to write

def foo():
    return expr

In the example the function is

def Trie():
    return collections.defauldict(Trie)

This function creates a defaultdict whose values automatically spring into 
existence and are defaultdict themselves:


>>> Trie = lambda: collections.defaultdict(Trie)
>>> trie = Trie()
>>> trie["a"]["b"]["c"]
defaultdict(<function <lambda> at 0x7f220e21cae8>, {})
>>> trie
defaultdict(<function <lambda> at 0x7f220e21cae8>, {'a': 
defaultdict(<function <lambda> at 0x7f220e21cae8>, {'b': 
defaultdict(<function <lambda> at 0x7f220e21cae8>, {'c': 
defaultdict(<function <lambda> at 0x7f220e21cae8>, {})})})})

You can achieve the same with the standard dict by checking explicitly for 
the key:

>>> trie = {}
>>> t = trie
>>> for key in ["a", "b", "c"]:
...     if key not in t:
...         t[key] = {}
...     t = t[key]
... 
>>> trie
{'a': {'b': {'c': {}}}}

Can you rewrite this with the dict.setdefault() method?

The reduce() function is basically a single loop:

>>> def reduce(func, items, initial):
...     result = initial
...     for item in items:
...         result = func(result, item)
...     return result
... 
>>> reduce(lambda a, b: a + b, [1, 2, 3], 42)
48

Rewritten without reduce:

>>> result = 42
>>> for item in [1, 2, 3]:
...     result = result + item
... 
>>> result
48

If we rewrite your code following the examples above we get

trie = {}
END = True

for i, word in enumerate(words):
    t = trie
    for c in word:
        t = t.setdefault(c, {})
    t[END] = i
print(trie.values())

which you may find a bit easier to follow.

You are not alone.