Как реализовать общую иерархию структур с внедренной функциональностью

Question

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

Я начал с этой иерархии:

interface BinaryTree<Node> {
    Node left(Node);
    bool hasLeft(Node);

    Node right(Node);
    bool hasRight(Node);
}

interface BinaryTreeWithRoot<Node> : BinaryTree<Node> {
    Node root();
}

interface BinaryTreeWithParent<Node> : BinaryTree<Node> {
    Node parent(Node);
    bool hasParent(Node);
}

Теперь, в принципе, я хочу иметь возможность реализовать концепцию поддерева универсальным способом: Для каждого класса T: BinaryTree мне нужно поддерево 'class' (T), которое обеспечивает ту же функциональность T (поэтому оно должно быть производным от него), а также переписывает функциональность root ().

Примерно так:

class Subtree<T, Node> : T, BinaryTreeWithRoot<Node> 
    where T : BinaryTree<Node>
{
    T reference;
    Node root;

    void setRoot(Node root) {
        this.root = root;
    }

    override Node BinaryTreeWithRoot<Node>::root() {
        return this.root;
    }

    // Now, inherit all the functionality of T, so an instance of this class can be used anywhere where T can.
    forall method(arguments) return reference.method(arguments);
}

Теперь с этим кодом я не уверен, как создать объект типа поддерево, так как объект дерева каким-то образом должен быть внедрен.

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

Итак, одним из подходов к этому являются миксины, которые позволяют универсальному классу наследовать от своего параметра шаблона.

Мне также интересно, как такая иерархия может быть реализована в Haskell, поскольку в Haskell есть отличная система типов, и я думаю, что будет проще внедрить такую ​​функциональность.

Например, в Haskell это может быть что-то вроде:

class BinaryTree tree node where
    left :: tree -> node -> node
    right :: tree -> node -> node

class BinaryTreeWithRoot node where
    left :: tree -> node -> node
    right :: tree -> node -> node -- but this is a duplication of the code of BinaryTree
    root :: tree -> node

instance BinaryTree (BinaryTreeWithRoot node) where
    left = left
    right = right

data (BinaryTree tree node) => Subtree tree node = 
 ...

instance BinaryTreeWithRoot (Subtree tree node) where ...

Мне интересно, если и как это можно сделать на языке oop (c ++, c #, d, java), так как c ++ и d предоставляют миксины из коробки (и я не уверен в d), и из любопытства с системой типов Haskell.

Answer 1

Поскольку в D есть «настоящие» шаблоны, а не шаблоны, сделать наследование класса шаблона из его параметра шаблона тривиально:

class A {}
class B(T) : T {
    static assert(is(B!T : T));  // Passes.
}

Что касается работы Subtree в D, то что-то вроде этого должно произойтисделайте это, предполагая, что у вас также есть шаблон класса Node:

class Subtree(T) : T, BinaryTreeWithRoot!(Node!(T))
{
    T reference;
    Node root;

    void setRoot(Node root) {
        this.root = root;
    }

    override Node root() {
        return this.root;
    }
}

Однако, IIUC (поправьте меня, если я ошибаюсь), T является полезной нагрузкой дерева и поэтому может бытьпримитивный.Если это так, вам лучше получить возможность использовать Subtree!(T) в качестве T через alias this, который позволяет выполнять подтипы без наследования и работает с примитивами:

class Subtree(T) : BinaryTreeWithRoot!(Node!(T))
{
    T reference;
    alias reference this;  // Make this implicitly convertible to reference.
    Node root;

    void setRoot(Node root) {
        this.root = root;
    }

    override Node root() {
        return this.root;
    }
}

Answer 2

Создание такого древовидного интерфейса в Haskell ... необычно. И Node, и Subtree являются лишними. Частично это связано с алгебраическими типами, а частично потому, что данные на Haskell неизменны, поэтому для выполнения определенных задач требуются разные методы (например, установка корневого узла). Это можно сделать, интерфейс будет выглядеть примерно так:

class BinaryTree tree where
    left :: tree a -> Maybe (tree a)
    right :: tree a -> Maybe (tree a)

-- BinaryTreeWithRoot inherits the BinaryTree interface
class BinaryTree tree => BinaryTreeWithRoot tree where
    root :: tree a -> tree a

Затем, с довольно стандартным двоичным определением дерева:

data Tree a =
  Leaf
  | Branch a (Tree a) (Tree a)

instance BinaryTree Tree where
  left Leaf = Nothing
  left (Branch _ l r) = Just l
  right Leaf = Nothing
  right (Branch _ l r) = Just r

data TreeWithRoot a =
  LeafR (TreeWithRoot a)
  | BranchR a (TreeWithRoot a) (TreeWithRoot a) (TreeWithRoot a)

instance BinaryTree TreeWithRoot where
-- BinaryTree definitions omitted

instance BinaryTreeWithRoot TreeWithRoot where
  root (LeafR rt) = rt
  root (BranchR _ rt l r) = rt

Поскольку этот интерфейс возвращает Maybe (tree a), вы также можете использовать left и right, чтобы проверить, существуют ли ветви, вместо использования отдельных методов.

В этом нет ничего особенно плохого, но я не верю, что когда-либо видел, чтобы кто-то действительно реализовывал этот подход. Более обычные методы - либо определить обходы в терминах Foldable и Traversable, либо создать молнию . Застежки-молнии просты для извлечения вручную, но есть несколько общих реализаций молний, ​​таких как zipper , pez и syz .

Answer 3

В C # 4 я бы использовал динамику для достижения этой цели. Например, вы можете попробовать определить класс SubtTree как:

public class Subtree<T, Node> : DynamicObject, BinaryTreeWithRoot<Node> where T : BinaryTree<Node>
{
    private readonly T tree;

    public Subtree(T tree)
    {
        this.tree = tree;
    }
}

и переопределить соответствующие методы DynamicObject, используя методы / свойства дерева. Дополнительную информацию (и пример кода) можно найти в этом замечательном сообщении в блоге о Использование динамического C # 4.0 для существенного упрощения вашего личного кода отражения .

Стоит отметить, что из-за использования динамических возможностей и отражения будут введены небольшие издержки производительности, а также снижена безопасность (поскольку это может повлечь за собой нарушение инкапсуляции).

Answer 4

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

Кроме того, кодирование с проверками hasLeft / hasRight означает, что каждый доступ является двухэтапным процессом. Проверка существования фиксированной позиции не обеспечит эффективные алгоритмы. Вместо этого, я думаю, вы обнаружите, что добавление универсального свойства, которое может быть двоичным слева / справа или двоичным красным / черным или индексом символа или чем-то еще, позволит гораздо больше повторного использования ваших алгоритмов и проверки того, что данные могут выполняться только этими алгоритмами это нужно (конкретные двоичные алгоритмы).

В семантическом представлении вы хотите сначала закодировать некоторые базовые свойства, а затем специализироваться. Когда вы находитесь «в» узле внутри алгоритма, вы хотите сначала найти дочерние элементы dge . Это должен быть контейнерный диапазон структур ребер, которые позволяют вам переходить к дочерним узлам. Поскольку это может быть универсальный контейнер, в нем может быть 0, 2, 5, 1 или даже 100 ребер. Многим алгоритмам все равно. Если он имеет 0, перебор диапазона ничего не даст - не нужно проверять hasX или hasY. Для каждого ребра вы должны иметь возможность получить дочерний узел и выполнять поиск по любому алгоритму, который вы пожелаете.

Этот подход в основном используется в своей библиотеке графов и позволяет расширять алгоритмы дерева до графов, где они применимы, для еще большего повторного использования универсального алгоритма.

Так что у вас уже есть базовый интерфейс с этим

TreeNode:
  getChildEdges: () -> TreeEdgeRange

TreeEdge:
  getChildNode: () -> TreeNode

и все, что вам нравится в вашем любимом языке. Например, D имеет особенно полезный синтаксис диапазона.

Вы захотите иметь некоторый базовый объект Tree, который дает вам узлы. Что-то вроде

Tree:
  getTreeNodes: () -> TreeNodeRange

начинает вас.

Теперь, если вы хотите поддерживать BinaryTrees, сделайте это как ограничение для этого интерфейса. Обратите внимание, что на самом деле вам не нужны никакие новые методы интерфейса, вам просто нужно применять больше инвариантов - каждый TreeNode имеет 0, 1 или 2 childEdges. Просто создайте тип интерфейса, который указывает на это семантическое ограничение:

BinaryTree : Tree

И если вы хотите поддерживать корневые деревья, добавьте интерфейсный слой с

RootedTree : Tree:
  getRoot: () -> TreeNode

добавляет эту возможность.

Основная идея заключается в том, что вам не нужно добавлять методы интерфейса для добавления семантических требований, если вы делаете свои классы более специфичными в иерархии. Добавляйте методы интерфейса только в том случае, если есть новое семантическое поведение, к которому требуется доступ. В противном случае - применять новые инварианты в универсальном интерфейсе.

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

PropertiedTreeNode<Property> : TreeNode:
  getProperty: () -> Property

PropertiedTreeEdge<Property> : TreeEdge:
  getProperty: () -> Property

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

Если вы следуете указанным выше правилам приравнивания типов к семантическим описаниям, то ваше поддерево должно быть очевидным - оно точно того же типа, что и дерево, из которого оно исходит! На самом деле у вас вообще не должно быть типа SubTree. Вместо этого вы должны просто иметь метод определенного типа TreeNode, с которым вы имеете дело

PropertiedTreeNode<Property>:
  getSubTree: () -> PropertiedTree<Property>

И, как и в Boost, когда вы кодируете больше информации о возможностях Tree в его общих свойствах, вы можете получать новые типы Tree с более широкими интерфейсными контрактами.

Answer 5

Как вы указали, один из подходов заключается в создании класса поддерева для каждого класса дерева, который я создаю, Это означает дублирование кода, но его можно как-то «избежать» или, что лучше, автоматизировать, используя отражение и T4. Я сделал это сам для прошлого проекта, и он работает довольно хорошо!

Вы можете начать с блога Олега Синча для обзора T4. Вот хороший пример автоматически сгенерированных классов: http://www.olegsych.com/2007/12/how-to-use-t4-to-generate-decorator-classes/

Answer 6

Вы можете сделать: -

public class Node {
    public Node Left {get; set:}
    public Node Right {get; set;}
    public Node Parent {get; set;}  // if you want to be able to go up the tree
    public Node Root {get; set;}    // only if you want a direct link to root
}

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

Сделайте это универсальным Node<T> и сохраните значение тоже. Если вам не нравятся публичные сеттеры, сделайте их приватными и устанавливайте их только в конструкторе или в некоторых безопасных AddLeft(...) и т. Д. Методах.

Вы также можете избавиться от Root и просто переходить по ссылкам Parent, пока не найдете нулевое значение Parent (или не достигнете верхнего узла для своего случая поддерева).