c# - 如何实现具有注入(inject)功能的通用结构层次结构

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，我想要一个“类”Subtree(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);
}

现在有了这段代码，我不确定如何创建子树类型的对象，因为应该以某种方式注入(inject)树对象。

一种方法是为我创建的每个树类创建一个子树类，但这意味着代码重复，而且毕竟是一回事。

因此，一种方法是混入，它允许从其模板参数派生通用类。

我也很感兴趣如何在 Haskell 中实现这样的层次结构，因为 Haskell 有一个很棒的类型系统，我认为注入(inject)这样的功能会更容易。

例如在 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 是树的有效负载，因此可能是原语。如果是这种情况，您最好通过 alias this 获得将 Subtree!(T) 用作 T 的能力| ，它允许在没有继承的情况下进行子类型化，并与原语一起工作:

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;
    }
}