获取Data.Tree中的节点的父节点(haskell)

Question

我需要一个树实现,我可以访问树中任何节点的父节点.看看Data.Tree我看到了树的定义:

data Tree a = Node {
    rootLabel :: a,         -- ^ label value
    subForest :: Forest a   -- ^ zero or more child trees
}

所以如果我有一个树节点,Tree a我可以访问它的标签及其子节点.但是也可以访问其父节点？是否必须根据我的需求选择不同的实施方案？你会推荐哪个套餐？

Answer 1

如果我没有弄错的话,你所要求的基本上是LYAH关于Zippers的部分.

我不会试图比Miran更好地解释它,但基本的想法是在你穿越树时跟踪你来自哪棵树,以及你正在向下移动的那个树枝.您没有直接在数据结构中跟踪节点的父节点,但是当您遍历树时,所有信息都可用.

Answer 2

Data.Tree故意没有节点引用自己的父母.这样,对父节点(或其他分支中的节点)的更改不需要重新创建整个树,并且内存中的节点可以与多个树共享.像这样的结构这个术语是"持久的".

您可以实现一个知道自己父节点的节点; 结果结构将不会持久化.明确的选择是始终知道树的根节点在哪里; 这是任何语言的好习惯.

一个允许Data.Tree了解其父母的库是rosezipper,文档可以在这里找到.