如何在Haskell中编写一个对象树，并指向父对象和子对象？ [英] How do I code a tree of objects in Haskell with pointers to parent and children?

问题描述

我遇到了以下问题：我有一个不同类的对象树，其中子类中的操作使父类无效。在命令式语言中，这是微不足道的。例如，在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; 
} 
} 
 
公共类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代码，我会非常感激。编辑：我试图解决的问题如下：

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

在原始论文的术语中，修改一个可能需要频繁访问根和返回路径的树似乎是一个带有疤痕的Zipper数据结构变体的完美工作。休特;来自纸张的代码样本也建议使用记忆拉链的名称。当然，在一些照顾下，也可以使用普通拉链，但增强版可能更方便和/或更有效。

基本思想是与常规拉链后面的拉链一样，它已经允许人们以纯粹的功能方式在树上上下移动（没有任何明确的后向指针），但是向上操作和随后的下移操作变成了没有操作，将焦点留在原始节点上（而使用常规拉链将其移动到原始节点的最左边的兄弟节点）。

该文件：GérardHuet ，功能珍珠：拉链 。它只有六页，但其中包含的想法对任何功能程序员都非常有用。

I've got the following problem: I have a tree of objects of different classes where an action in the child class invalidates the parent. In imperative languages, it is trivial to do. For example, in 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
    }
}

How do I do the above in Haskell? I cannot wrap my mind around this, since once I construct an object in Haskell, it cannot be changed.

I would be much obliged if the relevant Haskell code is posted.

EDIT: the problem I am trying to solve is the following:

I have an application that edits documents. A document is a hierarchy of objects. When properties of children objects are modified, the document needs to be set to an invalid state, so as that the user knows that the document needs to be validated.

解决方案

Modifying a tree which might require frequent excursions up the path to the root and back seems like the perfect job for a variant of the Zipper data structure with "scars", in the terminology of the original paper by Huet; the code samples from the paper also suggest a name of "memorising zipper". Of course, with some care, a regular zipper could also be used, but the augmented version might be more convenient and/or efficient to use.

The basic idea is the same as that behind a regular zipper, which already allows one to move up and down a tree in a purely functional manner (without any explicit back-pointers), but a "go up" operation followed by a "go down" operation becomes a no-op, leaving the focus at the original node (whereas with the regular zipper it would move it to the leftmost sibling of the original node).

Here's a link to the paper: Gérard Huet, Functional Pearl: The Zipper. It's just six pages, but the ideas contained therein are of great usefulness to any functional programmer.

这篇关于如何在Haskell中编写一个对象树，并指向父对象和子对象？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！