如何使用指向父级和子级的指针在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

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

基本思路与普通拉链背后的理念相同,它已经允许一个人以纯粹的功能方式上下移动树(没有任何明确的后退指针),但是"上行"操作后面跟着"去"向下"操作变为无操作,将焦点留在原始节点上(而使用常规拉链则将其移动到原始节点的最左边的兄弟节点).

这是纸张的链接:GérardHuet,功能珍珠:拉链.这只是六页,但其中包含的想法对任何功能程序员都非常有用.

Answer 2

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

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

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

编辑：

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

希望这是有道理的。：s

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