Иерархические структуры

Эта заметка является логическим продолжением статьи: Cвойство замыкания, на примере list. Представление последовательностей в виде списков естественно распространить на последовательности, элементы которых сами могут быть последовательностями. Например, мы можем рассматривать объект ((1,2) 3, 4), получаемый с помощью ((1,2),(3, 4)). Как список с тремя членами, первый из которых сам является списком. В сущности, это подсказывается формой, в которой результат печатается интерпретатором. Еще один способ думать о последовательностях последовательностей — деревья (trees). Элементы последовательности являются ветвями дерева, а элементы, которые сами по себе последовательности — поддеревьями. Рисунок снизу показывает структуру в виде дерева.
*-Нравится статья? Кликни по рекламе! :)

Естественным инструментом для работы с деревьями является рекурсия, поскольку часто можно свести операции над деревьями к операциям над их ветвями, которые сами сводятся к операциям над ветвями ветвей, и так далее, пока мы не достигнем листьев дерева. Например, сравним процедуру length из предыдущей статьи с процедурой countLeaves, которая подсчитывает число листьев дерева. Чтобы реализовать countLeaves, вспомним рекурсивную схему вычисления length:

• Длина списка x есть 1 плюс длина cdr от x.
• Длина пустого списка есть 0.

countLeaves очень похожа на эту схему. Значение для пустого списка остается тем же:

• countLeaves от пустого списка равна 0.

Однако в шаге редукции, когда мы выделяем car списка, нам нужно учесть, что car сам по себе может быть деревом, листья которого нам требуется сосчитать. Таким образом, шаг редукции таков:

• countLeaves от дерева x есть countLeaves от (car x) плюс countLeaves от (cdr x).

Наконец, вычисляя car-ы, мы достигаем листьев, так что нам требуется еще один базовый случай:

• Count-leaves от листа равна 1.

Писать рекурсивные процедуры над деревьями в Python помогает элементарный предикат isinstance(l, tuple), который проверяет, является ли его аргумент кортежем. Вот процедура целиком:

def countLeaves(l):
    if l is None:
        return 0
    elif not isinstance(l, tuple):
        return 1
    return countLeaves(car(l))+countLeaves(cdr(l))

Порядок первых двух ветвей существен, поскольку пустой список удовлетворяет предикату is None и при этом не является парой.

Отображение деревьев
Подобно тому, как map может служить мощной абстракцией для работы с последовательностями, map, совмещенная с рекурсией, служит мощной абстракцией для работы с деревьями. Процедура scaleTree принимает в качестве аргумента числовой множитель и дерево, листьями которого являются числа. Она возвращает дерево той же формы, где каждое число умножено на множитель. Рекурсивная схема scaleTree похожа на схему countLeaves:

def scaleTree(tree, factor):
    if tree is None:
        return None
    elif not isinstance(tree, tuple):
        return tree*factor
    else:
        return (scaleTree(car(tree), factor), scaleTree(cdr(tree), factor))

Другой способ реализации scaleTree состоит в том, чтобы рассматривать дерево как последовательность поддеревьев и использовать map. Мы отображаем последовательность, масштабируя по очереди каждое поддерево, и возвращаем список результатов. В базовом случае, когда дерево является листом, мы просто умножаем. Нужно только быть аккуратнее, мы не можем использовать map в чистом виде, который мы описали с вами в прошлой статье. Её нужно немного модифицировать с учетом, что элементы сами являются последовательностями.
Получаем:

def map(proc, l):
    if l is None:
        return None
    elif not isinstance(l, tuple):
        return proc(l)
    return (proc(car(l)), map(proc,cdr(l)))

def scaleTree(tree, factor):
    f=lambda subTree:mapScaleTree(subTree, factor) if isinstance(subTree, tuple) else subTree*factor
    return map(f, tree)

Многие операции над деревьями могут быть реализованы с помощью такого сочетания операций над последовательностями и рекурсии.


Используемая литература:

1. http://mitpress.mit.edu/sicp/