Этюды на питоне: однострочное дерево

Взято из https://gist.github.com/,  http://recursive-labs.com/

В недрах интернета есть сотни реализаций дерева на питоне, но сегодня мне хотелось бы рассказать о самой короткой из реализаций, требующей при этом довольно приличного понимания некоторых идей, лежащих в основе python. Вот она:

from containers import defaultdict
def tree(): return dafaultdict(tree)

Это действительно все!
Пользоваться этим тоже элементарно:

>>> a = tree()
>>> a['foo']['bar'] = 'foobar'
>>> a['free']['beer'] = 'free beer' 
>>> print a['free']['beer']
free beer

Чтобы лучше увидеть, что получилось, можно преобразовать это в json:

>>> import json
>>> print(json.dumps(a))
{"foo": {"bar": "foobar"}, "free": {"beer": "free beer"}}

 Теперь разберемся, как это работает.

Словари в качестве деревьев

Обычные словари в python вполне подходят для реализации деревьев, например конструкция:

b = {1: {2:{}, 3:{}}}

Представляет простое дерево:

  1

 / \

2   3

В листках дерева находятся словари, чтобы туда можно было присоединить другое дерево, например так:

 b[1][3] = {4:{5:{}, 6:{}}}

    1

   / \

  2   3

       \

        4

       / \ 

      5   6

В качестве листьев могли бы выступать и любые значения:

>>> c = {1: {2:True, 3:False}

>>> print(c[1][3])

False

    1

   / \

  2   3

  |   |

True False

 

Переменные и функции

Функции в python являются объектами первого рода, а это значит что с ними можно работать как с любыми другими переменными, в том числе создавать динамически и присваивать переменным. Динамическое создание нас сейчас не интересует, а вот присваивание понадобится. Работает оно так:

>>> def sqr(num):

>>>     return num*num

>>> func1 = sqr 

>>> print(func(3))

9 

В том числе функцию можно присваивать как значение элементу словаря:

>>> d = {}

>>> d[1] = func1

>>> d[2] = str

>>> d[1](4)

16 

defautdict

defaultdict из модуля collections похож на обычный dict за тем исключением, что в случае отсутствия в словаре запрашиваемого ключа, вместо вызова исключения KeyError, будет возвращено значение, возвращенное функцией, переданной конструктору defaultdict.

>>> def const():

>>>     return 999

>>> e = defaultdict(const)

>>> print(e[1])

999

>>> e[1] = 1

>>> print(e[1])

1 

Теперь все вместе

Теперь должно быть совсем понятно, как работает наше дерево:

>>> def tree(): return defaultdict(tree)

>>> t = tree()

>>> print(json.dumps(t))

 {}

сейчас в переменной t дерево без листьев, или просто пустой словарь. Чтобы добавить их в него, выполним:

>>> t[1]

>>> t[1][2]

>>> t[1][3][4]

>>> print json.dumps(t)

{"1": {"2": {}, "3": {"4": {}}}}

На всякий случай вспомним, что dict в питоне mutable структура данных. Каждое обращение по некоторому ключу в возвращает уже находящееся там значение, либо создает в словаре новый ключ и присваивает ему значение по умолчанию - нашу функцию tree. 

Вот собственно и все.