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 代码，我将不胜感激。

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

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

4

6 回答 6

7

用 Huet 的原始论文的术语来说，修改可能需要频繁沿路径向上到根并返回的树似乎是带有“疤痕”的 Zipper 数据结构变体的完美工作；论文中的代码示例还建议使用“记忆拉链”的名称。当然，需要注意的是，也可以使用普通拉链，但增强版可能更方便和/或更有效地使用。

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

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

于 2010-06-07T16:01:15.990 回答
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) []

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

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

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

于 2010-06-07T15:28:05.333 回答
3

这是一些 zipper 代码，演示了轻松修改光标指向的数据以及树的“全局”属性。我们构建一棵树，将光标移动到最初包含 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
于 2010-06-07T16:52:36.813 回答
2

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

  1. 你不能有一个 2-way 列表，树上的孩子指向他们的父母，等等。*
  2. 仅仅改变一个节点通常是不够的。任何更改的节点都需要从数据结构的“根”一直到您希望更改的节点的每个节点中进行更改。

底线是，我不会尝试采用 Java（或任何其他命令式语言）算法并尝试将其转换为 Haskell。相反，尝试找到一种功能更强大的算法（甚至可能是不同的数据结构）来解决问题。

编辑：

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

希望这是有道理的。：秒

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

于 2010-06-07T15:23:33.080 回答
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

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

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

于 2010-06-08T10:56:33.280 回答
0

研究使用Functor该类型的实例Maybe。

例如，也许你的问题是这样的：你想将一个元素插入到二叉树中，但前提是它不存在。你可以这样做：

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插入元素的新树。

希望这与您尝试做的任何事情有关。

于 2010-06-07T15:57:55.843 回答