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.
_______________________________________________
Tutor maillist - Tutor@python.org
To unsubscribe or change subscription options:
https://mail.python.org/mailman/listinfo/tutor
