[Tutor] Python creating trie

[Steven D'Aprano]

On Sun, Nov 12, 2017 at 02:37:06AM -0800, anish singh wrote:
> Can someone explain me this code to create a trie
> from words?

Not really. What makes this a trie? Where did you get this code from?


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

The lambda is exactly equivalent to:

# Trie = lambda: collections.defaultdict(Trie)
def Trie():
    return collections.defaultdict(Trie)


Does that help?

The call to reduce (inside the loop) can be re-written as (untested):

# for i, word in enumerate(words):
#     reduce(dict.__getitem__, word, trie)[END] = i
for i, word in enumerate(words):
    value = trie
    for item in word:
        value = value[item]
    value[END] = i



-- 
Steve