我该如何在Haskell中编写一个对象树并使用指向父节点和子节点的指针？

Question

我该如何在Haskell中编写一个对象树并使用指向父节点和子节点的指针？

javahaskellfunctional-programmingimperative

8

我有一个问题：我有一个由不同类的对象组成的树形结构，在子类中的某个操作会使得其父类无效。在命令式语言中，这很容易实现。例如，在Java中：

public class A {
    private List<B> m_children = new LinkedList<B>();
    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代码，我将不胜感激。

编辑：我要解决的问题是：

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

- axilmar

1

在sepp2k和Tal Pressman的回答基础上，您还可以编写Haskell代码来完全模仿Java的做法，通过逃离纯函数世界并使用ST或IO单子来实现。使用STRef作为“可变”指针。 - yairchu

1

有趣。它是如何工作的？编译器是否将STRef视为特殊结构？STRef和IORef之间有什么区别？我已经谷歌过了，但没有找到易于理解的内容。 - axilmar

6个回答

3

回答您标题中的问题：是的，您可以创建具有链接到其父节点和子节点的节点。示例：

--               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) []

问题在于它是否对您特定的用例有用（通常情况下并不是）。现在在您的问题中：您是正确的，一旦创建了一个值，就无法更改该值。因此，一旦您拥有有效的树，只要引用该树的变量在范围内，您将始终拥有有效的树。您没有真正描述您要解决的问题，因此我无法告诉您如何实现您要做的事情的功能模型，但我相信有一种方法可以避免改变树的结构。

- sepp2k

我要解决的问题是：我有一个编辑文档的应用程序。一个文档是一个对象层次结构。当子对象的属性被修改时，文档需要设置为无效状态，以便用户知道文档需要验证。 - axilmar

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

- Anthony

谢谢。据我所了解，上述代码执行以下操作： 1）在主函数中创建一棵树。 2）通过获取光标来获取一个子节点。 3）设置数据，使树失效并返回新的根树。失效是这样发生的：使用新的有效标志和树的其余部分构造出一个新的根节点。我理解得对吗？ - axilmar

是的，但需要注意的是，setData() 不仅仅会给你新树的根节点，而是一个带有光标位置的新树（因此您可以继续进行后续的本地更改）。 - Anthony

另一个需要注意的是，当根节点已经无效时，可以通过不重建树来使代码更加高效。 - Anthony

如果根节点在无效时调用回调怎么办？在Java中，我可以有一个对象列表，当对象无效时通知它们。在Haskell中该怎么做呢？每次向对象添加新的回调时，我需要重新构建对象吗？那些没有更新的先前根节点的引用呢？在Java中，根节点中的一个成员更新会反映在所有引用该对象的对象中。 - axilmar

很难对这些问题提供完全通用的答案。请记住，重建根节点是一项非常便宜的操作，因为悬挂在其下的子树不受影响。此外，使用像这里所做的zipper意味着没有持久引用旧根节点的问题。因此，添加新回调涉及重建根节点，但这并不是什么大问题。如果您有其他特定的问题情况，我鼓励您从类似于此代码的东西开始，并将其作为另一个问题发布，以便您可以获得一些具体的回复。 - Anthony

2

我对Haskell没有太多经验，但据我所知，在纯函数语言中不可能有参考图中的环。这意味着：

你不能拥有双向列表、指向其父节点的树的子节点等。
通常改变一个节点是不够的。任何被更改的节点都需要从数据结构的“根”开始到您希望更改的节点的每个节点进行更改。

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

编辑：

从您的澄清中并不完全清楚您是否只需要使更改的对象的直接父项无效，还是所有祖先在层次结构中都无效，但这并不重要。由于使对象无效基本上意味着更改它而且这是不可能的，因此您基本上必须创建该对象的修改副本，然后您必须使其父项也指向它，因此您还必须为其创建一个新对象。这一过程一直持续到根部。如果您有一些递归来遍历树以“修改”您的对象，那么您可以在递归退出时重新创建从该对象到根的路径。

希望这讲得通。：s

*正如jberryman和其他答案在评论中指出的那样，使用惰性求值可以在Haskell中创建循环引用图。

- Tal Pressman

4

实际上这并不正确。在 Haskell 中，惰性使我们能够以非常复杂的方式（搜索“tying the knot”）定义一个数据结构，即使是以其自身为基础。因此，双向链表也没有问题。但当您尝试修改列表元素之一时，就会遇到麻烦 :) - jberryman

0

可以尝试使用 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' l r)
    | a == a' = Nothing
    | a < a'  = fmap (\l'-> Node a' l' r) (maybeInsert a l)
    | a > a'  = fmap (\r'-> Node a' l r') (maybeInsert a r)

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

希望这与您正在尝试完成的内容相关。

- jberryman

0

懒惰模式能否确保验证不会发生太频繁？这样，您就不需要存储m_valid字段。

例如，如果只在保存时进行验证，则可以随心所欲地编辑对象，而无需一直重新验证；仅当用户按下“保存”按钮时，才计算validateDoc的值。由于我不确定您对有效的概念和所需的内容，因此我可能完全错了。

未经尝试和不完整的代码：

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

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

顺便说一句，我认为你在main中忘记了一个a.addChild(b);。

- yatima2975

有效的文档意味着它通过了某个测试。这里的想法是用户编辑文档，然后对其进行验证。 - axilmar

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Michał Marczyk · Accepted Answer

修改树可能需要频繁往返于路径和根节点之间，这似乎是“有痕迹”的Zipper数据结构的完美应用场景，即在Huet的原始论文中使用的术语中; 该论文中的代码示例还建议使用“记忆Zipper”名称。当然，经过一些小心处理，也可以使用常规Zipper，但增强版本可能更方便和/或高效。

基本思想与常规Zipper相同，后者已允许以纯函数方式（没有任何显式的反向指针）上下移动树，但“向上”操作后跟“向下”操作变为无操作，将焦点留在原始节点处（而使用常规Zipper则会将其移动到原始节点的最左边的兄弟节点）。

这是论文链接：Gérard Huet，“Functional Pearl: The Zipper”。它只有六页，但其中包含的思想对任何功能程序员都非常有用。