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

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

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

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 мне нужно «поддерево класса» (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.