Деревья

В математике деревом называется произвольный связный ациклический неориентированный граф. В информатике же под деревом по-умолчанию понимают существенно более конкретную структуру, называемую в математике рекуррентным или алгебраическим деревом. Говоря неформально, дерево — это либо «лист», либо последовательность деревьев.

Дерево как АДТ

Несколько более формально можно дать следующее определение: дерево — это абстрактный тип данных (АДТ), изоморфный следующему

def leaf(x):
    return ("leaf", x)

def branch(x, trees):
    return ("branch", x, list(trees))
    
def reduce(tree, leaf_op, branch_op):
    if tree[0] == "leaf":
        return leaf_op(tree[1])
    elif tree[0] == "branch":
        return branch_op(
            tree[1], 
            [reduce(subtree, leaf_op, branch_op) 
                for subtree in tree[2]])
    else:
        raise RuntimeError("wrong tree")

Напомним, что под изоморфизмом типов данных имеется в виду биекция между этими типами, «коммутирующая» со всеми операциями, ассоциированными с этими типами.

Например, следующий тип данных (называемый катаморфным представлением или кодировкой Чёрча) тоже является деревом:

def cata_leaf(x):
    return (lambda l, b: l(x))

def cata_branch(x, trees):
    return (lambda l, b: b(x, [t(l,b) for t in trees]))
    
def cata_reduce(tree, leaf_op, branch_op):
    return tree(leaf_op, branch_op)

А вот — биекция между ними:

def tree_to_cata(tree):
    return lambda l, b: reduce(tree, l, b)
    
def cata_to_tree(cata):
    return cata(
        lambda x: ("leaf", x),
        lambda x, trees: ("branch", x, trees))

Или, если на неё посмотреть немного повнимательнее:

def tree_to_cata(tree):
    return reduce(tree, cata_leaf, cata_branch)

def cata_to_tree(cata):
    return cata_reduce(cata, leaf, branch)

Общее у двух вышеописанных моделей лишь поведение reduce относительно leaf и branch. А именно, выполняются следующие свойства:

• reduce(leaf(x), l, b) = l(x)
• reduce(branch(x,trees), l, b) = b(x, [reduce(t,l,b) for t in trees])

Именно они и задают дерево как абстрактный тип данных.

Что это вообще было?

Теперь поясним подробнее то, что сейчас произошло. Для того, чтобы всё встало на свои места, достаточно понять одну простую вещь:

• деревья — то же самое, что алгебраические формулы (с которыми вы общаетесь уже не менее 9 лет)

Слова «то же самое» нужно понимать совершенно буквально: деревья (в информатике) и алгебраические формулы (в математике) — одно и то же.

Например, вот формула:

foo(1,2) + 3*(4**5 + foo(6,7))

Вот — соответствующиее ей дерево:

branch("+", [
  branch("foo", [leaf(1), leaf(2)]),
  branch("*", [
    leaf(3),
    branch("+", [
      branch("**", [leaf(4), leaf(5)]),
      branch("foo", [leaf(6), leaf(7)])])])])

А таинственный на первый взгляд метод reduce всего лишь описывает процесс вычисления формулы для заданных интерпретаций операций, в ней фигурирующих. Например, чтобы получить из дерева выше значение формулы выше, аналогичное тому, которое получит интерпретатор языка Python, достаточно применить reduce к следующим аргументам:

def interpret_leaf(x): return x

def interpret_branch(op, args):
    a,b = args
    
    if op == "+": return a+b
    if op == "*": return a*b
    if op == "**": return a**b
    if op == "foo": return foo(a,b)

Кодировка Чёрча же всего лишь иллюстрирует тот факт, что формула — это то же самое, что и алгоритм её вычисления, параметризованный интерпретациями операций (а термином катаморфизм или свёртка называется как раз алгоритм вычисления формулы, параметризованный интерпретациями операций).