生成不可变的循环数据结构

Question

假设我有这个简单的类：

public class Pair {
    public readonly object first;
    public readonly object second;

    public Pair(object first, object second) {
        this.first = first;
        this.second = second;
    }
}

生成一组循环图是不可能的。

你该如何创建一个类似的类，仍然保持不可变性，但可以用来生成循环图呢？

- configurator

---

这对我来说似乎是不可能的，顺便说一下。 - configurator

一个好的答案将会是针对特定编程语言的。你应该在你偏爱的语言中标记它。 - Paul McMillan

使用惰性求值并递归定义循环。 - Dario

@Paul：术语“不可变”和“循环”的适用范围并不特定于某种编程语言 - 为什么答案会是特定于某种语言的呢？ - configurator

因为它们在实际应用中的工作方式在不同的语言之间是不同的。例如，在Python中很难回答这个问题... 因为那里真正不可变的东西非常少。 - Paul McMillan

Answer 1

表示图结构的方法有很多种。其中一种方法是使用矩阵。每行和每列都由顶点索引，矩阵中的每个单元格表示一个有向（可能带权重）边。一个简单的、循环的图，用0表示没有连接边，用1表示有连接边，就像这样:

| 0 1 |
| 1 0 |

与许多不可变结构一样，构建它们的方法是基于给定矩阵的所需关系返回新结构。例如，如果我们想要在上面的图形中将第一个顶点添加到自身的边缘，则表示该操作的矩阵就是。

| 1 0 |
| 0 0 |

而要将其与其他矩阵结合起来，我们只需将它们相加即可。

| 0 1 |  +  | 1 0 |  ==  | 1 1 |
| 1 0 |     | 0 0 |      | 1 0 |

当然，有很多方法可以表示矩阵，不同的方法在速度、空间和某些其他操作方面有不同的权衡，但这是一个不同的问题。

- SingleNegationElimination

Answer 2

我认为使用您提出的严格不可变类类型是不可能实现的。我能想到的唯一方法是添加一个带有setter的属性，检查字段是否为空，并允许在为空时进行设置。这样，您可以将第一个对象中的first字段保留为空，并在循环中创建最后一个对象后适当地设置该字段以关闭循环。一旦设置了它，它就不再为空，setter将不再允许更改它。当然，从类内部的代码仍然可以更改该字段，但从外部来看，它基本上是不可变的。

类似于以下内容（C＃）：

public class Pair {
    private object first;
    private object second;

    public Pair(object first, object second) {
        this.first = first;
        this.second = second;
    }

    public object First {
        get { return first; }
        set 
        {
            if (first == null)
            {
                first = value;
            }
        }
    }

    // and a similar property for second
}

- Andrew Cooper

---

注意线程安全...通常，不可变性与线程安全相关联，但在这种情况下，您的“Pair”类型的表面不可变性根本不会使其线程安全！例如，假设您有var a = new Pair(1, null); var b = new Pair(null, 2); b.first = a; a.second = b，然后发布由a引用的对象（以便其他线程可以看到它）。如果没有适当的同步，其他线程实际上可能会看到a.second == null！ - Bruno Reis

Answer 3

我会采用函数式的方法，将 continuation 传递到 ctor 中。或者，它也可以接受一系列类似元素作为参数（将 IEnumerable 视为参数）。

- GregC