Как изобразить отображение между двумя деревьями в Haskell? - PullRequest
Новая
       11

Как изобразить отображение между двумя деревьями в Haskell?

12 голосов
/ 15 апреля 2019

Я пытаюсь реализовать алгоритм обработки дерева в Haskell и (из-за того, что это моя первая программа на Haskell!), Я борюсь с проектированием структур данных. Может ли кто-нибудь из гуру ФП протянуть руку помощи?

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

Проблема

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

  • Алгоритм работает на двух розовых деревьях, X и Y.
  • На первом этапе алгоритма вычисляются некоторые производные свойства для каждого узла на основе его метки и атрибутов, а также свойств его потомков.
  • Эти производные свойства используются для вычисления частичного отображения между двумя деревьями, так что узел в X может быть связан с узлом в Y и наоборот. Поскольку сопоставление является частичным, любой узел в X или Y может быть сопоставлен (т. Е. Иметь партнера в другом дереве) или, альтернативно, может быть не отображен.
  • Финальная фаза алгоритма оптимизирует эти сопоставления посредством последовательности операций, которые проверяют родительские / дочерние / дочерние элементы сопоставленных узлов.

Следовательно, структуры данных должны иметь следующие характеристики:

  • При наличии ссылки на узел предоставьте доступ родителю этого узла, братьям и сестрам этого узла и дочерним узлам этого узла.
  • Учитывая узел во входном дереве, разрешите аннотацию этого узла с дополнительной информацией (производные свойства и необязательная ссылка на узел в другом дереве).

Эскиз императивного решения

Если бы я реализовал этот алгоритм с использованием императивного языка, решение выглядело бы примерно так:

Предположим, что отправной точкой является следующее определение дерева ввода: 

struct node {
    // Identifier for this node, unique within the containing tree
    size_t id;

    // Label of this node
    enum label label;

    // Attributes of this node
    // An attribute can be assumed to be a key-value pair
    // Details of the attributes themselves aren't material to this
    // discussion, so the "attribute" type is left opaque
    struct attribute **attributes;
    size_t n_attributes;

    // Pointer to parent of this node
    // NULL iff this node is root
    struct node *parent;

    // Pointer to first child of this node
    // NULL iff this node is leaf
    struct node *child;

    // Double-linked list of siblings of this node
    struct node *prev;
    struct node *next;
};

Указатели, встроенные в каждый узел, явно поддерживают обходы вверх / вниз / влево / вправо, требуемые алгоритмом.

Аннотация может быть реализована путем определения следующей структуры: 

struct algo_node {
    // Pointer to input node which has been wrapped
    struct node *node;

    // Derived properties computed by first phase of the algorithm
    // Details of the properties themselves aren't material to this
    // discussion, so the "derived" type is left opaque
    struct derived props;

    // Pointer to corresponding node in the other tree
    // NULL iff this node is unmatched
    struct node *match;
};

На первом этапе алгоритма создается algo_node для каждого node в каждом из входных деревьев.

Отображение из algo_node в node тривиально: следуйте за встроенным указателем *node. Сопоставление в другом направлении может поддерживаться путем сохранения algo_node s в массиве, индексированном id входного узла.

Это, конечно, только одна из возможных реализаций. Возможны многие варианты, включая

  • Абстрагирование связанного списка детей за интерфейсом list или queue вместо хранения трех необработанных указателей
  • Вместо того, чтобы связывать дерево ввода с деревом алгоритма через индексы, кодируйте отношения родитель / потомок / родной брат непосредственно в struct algo_node

Переезд в Хаскелл

Давайте начнем со следующего определения дерева ввода: 

data Tree = Leaf Label Attributes
          | Node Label Attributes [Tree]

Увеличение каждого узла с идентификатором может быть достигнуто следующим образом: 

data AnnotatedTree = Tree Int

addIndex :: Int -> AnnotatedTree -> (AnnotatedTree, Int)

indexedTree = addIndex 0 tree

Аналогично, мы можем написать функцию, которая вычисляет производные свойства: 

data AnnotatedTree = Tree DerivedProperties

computeDerived :: DerivedProperties -> AnnotatedTree -> (AnnotatedTree, DerivedProperties)

derivedTree = computeDerived DefaultDerived tree

Приведенные выше фрагменты могут быть скорректированы без особых усилий, так что AnnotatedTree содержит и индекс, и производные свойства.

Однако я не знаю, с чего начать с отображения отображений между двумя деревьями. Основываясь на чтении, у меня есть несколько недоделанных идей ...

  • Определите AnnotatedTree, чтобы он содержал путь от корня другого дерева к сопоставленному узлу - закодирован в виде списка индексов в каждом последующем дочернем списке, [Integer]
    • Используйте застежку-молнию (о которой я в настоящее время довольно плохо понимаю), чтобы получить доступ к сопоставленному узлу (или его родителю / потомкам / братьям и сестрам) по пути
    • Или, возможно, использовать линзу (... о которой я еще менее ясно понимаю), чтобы сделать то же самое
  • Определите AnnotatedTree для прямой ссылки на сопоставленный узел, как Maybe Tree
    • Но тогда я не вижу пути к родителю / братьям и сестрам сопоставленного узла

... но я мог бы действительно сделать некоторые рекомендации, по которым (если таковые имеются) из них стоит следовать.

Любая помощь будет высоко ценится!

...