如何使用指向父级和子级的指针在Haskell中编写对象树？

我遇到了以下问题：我有一个不同类的对象树，其中子类中的操作使父类无效。 在命令式语言中，这样做很简单。 例如，在Java中：

public class A { private List m_children = new LinkedList(); private boolean m_valid = true; public void invalidate() { m_valid = false; } public void addChild(B child) { m_children.add(child); child.m_parent = this; } } public class B { public A m_parent = null; private int m_data = 0; public void setData(int data) { m_data = 0; m_parent.invalidate(); } } public class Main { public static void main(String[] args) { A a = new A(); B b = new B(); b.setData(0); //invalidates A } } 

我如何在Haskell中执行上述操作？ 我无法解决这个问题，因为一旦我在Haskell中构造了一个对象，它就无法改变。

如果发布相关的Haskell代码，我将非常感激。

编辑：我想解决的问题如下：

我有一个编辑文档的应用程序。 文档是对象的层次结构。 当修改子对象的属性时，需要将文档设置为无效状态，以便用户知道需要validation文档。

Answer 1

在Huet原始论文的术语中，修改一个可能需要频繁偏移到根和后面的路径的树似乎是具有“疤痕”的Zipper数据结构的变体的完美工作; 来自论文的代码样本也提出了“记忆拉链”的名称。 当然，经过一些小心操作，也可以使用常规拉链，但增强版本可能更方便和/或更有效。

基本思想与普通拉链背后的基本思路相同，它已经允许一个人以纯粹的function方式上下移动树（没有任何明确的反向指针），但是“上行”操作后面跟着“去”向下“操作变为无操作，将焦点留在原始节点上（而使用常规拉链则将其移动到原始节点的最左边的兄弟节点）。

这是纸张的链接： GérardHuet， function珍珠：拉链 。 这只是六页，但其中包含的想法对任何function程序员都非常有用。

Answer 2

要回答标题中的问题：是的，您可以创建与父母及其子女有链接的节点。 例：

 -- parent children data Tree = Node (Maybe Tree) [Tree] root = Node Nothing [a,b] -- I can "forward reference" a and b because haskell is lazy a = Node (Just root) [] b = Node (Just root) [] 

问题是这是否对您的特定用例有用（通常不是这样）。

现在你身体里的问题是：你是对的，你不能在创建后改变它。 因此，一旦有了有效的树，只要引用该树的变量在范围内，您就会始终拥有一个有效的树。

你没有真正描述你想要解决的问题，所以我不能告诉你如何在function上模拟你想要做的事情，但我确信有一种方法可以不改变树。

Answer 3

下面是一些拉链代码，它演示了光标指向的数据的简单修改以及树的“全局”属性。 我们构建一个树，将光标移动到最初包含1的节点，将其更改为3，并在完全更新的树中留下指向该节点的光标。

 import Data.Maybe (fromJust) import Data.Tree import Data.Tree.Zipper type NodeData = Either Bool Int type TreePath a = [TreePos Full a -> TreePos Full a] firstChild' = fromJust . firstChild parent' = fromJust . parent prev' = fromJust . prev next' = fromJust . next -- Determine the path from the root of the tree to the cursor. pathToMe :: TreePos Full NodeData -> TreePath NodeData pathToMe t | isRoot t = [] | isFirst t = firstChild' : pathToMe (parent' t) | otherwise = next' : pathToMe (prev' t) -- Mark a tree as invalid, but leave the cursor in the same place. invalidate :: TreePos Full NodeData -> TreePos Full NodeData invalidate t = foldr ($) (setLabel (Left False) (root t)) (pathToMe t) -- Set a node's internal data. setData :: Int -> TreePos Full NodeData -> TreePos Full NodeData setData = (invalidate . ) . setLabel . Right main = let tree1 = Node (Left True) [Node (Right 1) [], Node (Right 2) []] Just cursor = firstChild (fromTree tree1) tree2 = setData 3 cursor in do putStrLn (drawTree (fmap show tree1)) putStrLn (drawTree (fmap show (toTree tree2))) putStrLn $ "Cursor at "++show (label tree2) 

输出：

 Left True | +- Right 1 | `- Right 2 Left False | +- Right 3 | `- Right 2 Cursor at Right 3 

Answer 4

我对Haskell没有多少经验，但据我所知，在纯函数式语言中不可能在参考图中使用圆圈。 这意味着：

1. 你不能有一个双向的名单，树上的孩子指着他们的父母，等等。*
2. 通常只更改一个节点是不够的。 任何更改的节点都需要在每个节点中进行更改，从数据结构的“根”开始一直到您要更改的节点。

最重要的是，我不会尝试使用Java（或任何其他命令式语言）算法并尝试将其转换为Haskell。 相反，尝试找到更多function算法（甚至可能是不同的数据结构）来解决问题。

编辑：

从您的澄清来看，您是否需要仅使更改的对象的直接父级或其所有祖先在该层次结构中无效，并不完全清楚，但这实际上并不重要。 由于使对象无效基本上意味着更改它并且这是不可能的，因此您基本上必须创建该对象的修改副本，然后您必须使其父指向它，因此您必须为此创建一个新对象。 这一直持续到你到达root。 如果你有一些递归来遍历树以便“修改”你的对象，那么你可以在离开递归的路上重新创建从该对象到根的路径。

希望有道理。 ：■

*正如jberryman的评论中指出的那样，在其他答案中，可以使用延迟评估在Haskell中创建循环引用图。

Answer 5

查看使用Maybe类型的Functor实例。

例如，也许您的问题是这样的：您希望将元素插入到二叉树中，但仅限于它尚未存在。 你可以这样做：

 data Tree a = Node a (Tree a) (Tree a) | Tip maybeInsert :: a -> Tree a -> Maybe (Tree a) maybeInsert a Tip = Just $ Node a Tip Tip maybeInsert a (Node a' lr) | a == a' = Nothing | a < a' = fmap (\l'-> Node a' l' r) (maybeInsert al) | a > a' = fmap (\r'-> Node a' l r') (maybeInsert ar) 

因此，如果我们发现元素已经存在，函数将返回Nothing ，或者返回Just插入元素的新树。

希望这与你想做的事情有关。

Answer 6

懒惰不能确保validation不会经常发生吗？ 这样，您就不需要存储m_valid字段。

例如，如果您只对保存进行validation，那么您可以根据心脏内容编辑对象，而无需一直重新validation; 只有当用户按下“保存”按钮时才会生成validateDoc计算值。 由于我不确定你的有效手段和你需要什么的概念，我可能完全是标记。

未经validation和不完整的代码：

 data Document = Document { subDocs :: [SubDoc] } data SubDoc = SubDoc { content :: String } addSubDoc :: SubDoc -> (Document -> Document) addSubDoc = error "not yet implemented: addSubDoc" modifySubDoc :: Int -> (SubDoc -> SubDoc) -> (Document -> Document) modifySubDoc = error "not yet implemented: modifySubDoc" validateDoc :: Document -> Bool validateDoc = all validateSubDoc . subDocs validateSubDoc :: SubDoc -> Bool validateSubDoc = not . null . contents 

我假设文档的整体有效性仅取决于子文档（这里通过确保它们包含非空字符串来模拟）。

顺便说一下，我想你忘记了a.addChild(b); 在main 。