我想为树结构实现一个通用层次结构,以后可以用一种与实现无关的方式来描述树上的通用算法.
我从这个层次结构开始:
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);
}
现在有了这段代码,我不知道如何创建一个类型子树的对象,因为树对象应该以某种方式注入.
一种方法是为我创建的每个树类创建一个子树类,但这意味着代码重复,毕竟它是同一个东西.
因此,一种方法是mixins,它允许泛型类从其模板参数派生.
我也很感兴趣如何在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提供了开箱即用的mixins(我不确定d),并且对Haskell类型系统的好奇心.
由于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)as作为Tvia 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;
}
}
在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
由于此接口返回a Maybe (tree a),您还可以使用left和right检查分支是否存在而不是使用单独的方法.
它没有什么特别的错,但我不相信我见过有人真正实现这种方法.更通常的技术是根据Foldable和/ Traversable或创建拉链来定义遍历.拉链很容易手动派生,但有几种通用拉链实现,如zipper,pez和syz.
我认为通过“BinaryTree”的方法假设了太多的固定结构，并且不必要地以非通用的方式定义您的接口。这样做会使您的树扩展到非二进制形式时难以重用算法。相反，当不必要或无用时，您将需要为多种样式编写界面代码。
此外，使用 hasLeft/hasRight 检查进行编码意味着每次访问都是一个两步过程。检查固定位置的存在不会提供有效的算法。相反，我认为您会发现添加一个通用属性（可能是二进制左/右或二进制红/黑或字符索引或其他任何内容）将允许更多地重用您的算法，并检查数据是否只能由这些算法完成需要它（特定的二进制算法）。
从语义的角度来看，您希望首先对一些基本属性进行编码，然后再进行专门化。当您位于算法内的某个节点时，您希望能够首先找到子边。这应该是边缘结构的容器范围，允许您导航到子节点。由于它可以是一个通用容器，因此它可以有 0、2、5、1 甚至 100 个边。许多算法并不关心。如果它为 0，则迭代该范围将不会执行任何操作 - 无需检查 hasX 或 hasY。对于每条边，您应该能够获取子节点，并递归您想要的任何算法。
这基本上是 boost 在其图形库中采用的方法，它允许将树算法扩展到适用的图形，以实现更好的通用算法重用。
所以你已经有了一个基本的界面
TreeNode:
getChildEdges: () -> TreeEdgeRange
TreeEdge:
getChildNode: () -> TreeNode
以及您最喜欢的语言喜欢的任何对象范围。例如，D 有一个特别有用的范围语法。
您将需要一些为您提供节点的基本 Tree 对象。就像是
Tree:
getTreeNodes: () -> TreeNodeRange
让你开始。
现在，如果您想支持二叉树，请将此作为对此接口的限制。请注意，您实际上并不需要任何新的接口方法，您只需要强制执行更多不变量 - 每个 TreeNode 有 0、1 或 2 个 childEdge。只需创建一个接口类型来指示此语义限制：
BinaryTree : Tree
如果你想支持有根树，添加一个接口层
RootedTree : Tree:
getRoot: () -> TreeNode
添加了该功能。
基本思想是，如果您要使类在层次结构中更加具体，则不必添加接口方法来添加语义要求。仅当有需要访问的新语义行为时才添加接口方法。否则 - 在通用接口上强制执行新的不变量。
最终，您需要使用保存有关节点或边的数据的结构来装饰节点和边，以便您可以构建 Tries 树和红黑树以及高级算法的所有出色工具。所以你会想要拥有
PropertiedTreeNode<Property> : TreeNode:
getProperty: () -> Property
PropertiedTreeEdge<Property> : TreeEdge:
getProperty: () -> Property
由于这是您希望允许通用算法处理的内容，因此属性是否是树的一部分的类型信息应该是通用的，并且算法可以忽略这些信息。这让你走上了boost的设计轨道，这些问题已经被非常优雅地解决了。如果您想了解如何构建通用树算法库，我建议您学习该库。
如果您遵循上述类型等同于语义描述的准则，那么子树应该是显而易见的 - 它与它所来自的树的类型完全相同！事实上，你真的根本不应该有 SubTree 类型。相反，您应该只拥有正在处理的特定 TreeNode 类型的方法
PropertiedTreeNode<Property>:
getSubTree: () -> PropertiedTree<Property>
而且，就像在 boost 中一样，当您在其通用属性中编码更多有关 Tree 功能的信息时，您可以获得具有更广泛接口契约的新 Tree 类型。