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

Question

我遇到了以下问题：我有一个不同类的对象树，其中子类中的操作使父类无效。在命令式语言中，这是微不足道的。例如，在 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 代码被发布，我将非常感激。

编辑：我试图解决的问题如下：

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

Answer 1

修改一棵树可能需要频繁地沿着路径往返于根部和返回，这对于具有“疤痕”的 Zipper 数据结构的变体来说似乎是完美的工作，用 Huet 原始论文的术语来说；论文中的代码示例还提出了“记忆拉链”的名称。当然，在小心的情况下，也可以使用常规拉链，但增强版本可能使用起来更方便和/或更有效。

基本思想与常规拉链背后的思想相同，它已经允许人们以纯粹的功能方式在树上上下移动（没有任何显式后向指针），但是“向上”操作后跟“去” down”操作变成无操作，将焦点留在原始节点（而使用常规拉链，它将把它移动到原始节点的最左边的兄弟节点）。

以下是该论文的链接：Gérard Huet，功能性珍珠：拉链。它只有六页，但其中包含的想法对任何函数式程序员都非常有用。

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

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

现在你体内的问题是：你是对的，值创建后就无法更改。因此，一旦您拥有一棵有效的树，只要引用该树的变量在范围内，您就始终拥有一棵有效的树。

您没有真正描述您想要解决的问题，所以我无法告诉您如何对您想要做的事情进行功能建模，但我确信有一种方法无需改变树。

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。相反，尝试找到更实用的算法（甚至可能是不同的数据结构）来解决问题。

编辑：

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

希望这是有道理的。 :s

*正如 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' 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)

因此，如果我们发现该元素已存在，则该函数将不返回任何内容，或者返回插入了元素的新树。

希望这与您想做的任何事情相关。

Answer 6

难道懒惰就不能确保验证不会太频繁地发生吗？这样，您就不需要存储 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); 。