为什么在Eric Lippert的不可变二叉树中没有循环？

Question

我只是看着Eric Lippert对不可变二叉树的简单实现,我对此有疑问.在显示实施后,Eric说明了这一点

请注意,不可变数据结构的另一个不错的功能是不可能(或故意!)创建包含循环的树.

似乎Eric的实现的这个特征不是仅仅来自不变性,而是来自树从树叶构建的事实.这自然会阻止节点将其任何祖先作为子节点.似乎如果你在另一个方向上构建了树,你就会引入循环的可能性.

我是否正确思考,或者在这种情况下循环的不可能性是否来自于不变性？考虑到来源,我想知道我是否遗漏了一些东西.

编辑:经过多思考后,似乎从叶子构建可能是创建不可变树的唯一方法.我对吗？

Answer 1

如果你真的想要努力,你可以创建一个树,其中包含不可变的循环.例如,您可以定义一个不可变的图类,然后说:

Graph g = Graph.Empty
  .AddNode("A")
  .AddNode("B")
  .AddNode("C")
  .AddEdge("A", "B")
  .AddEdge("B", "C")
  .AddEdge("C", "A");

嘿,你有一个带有"周期"的"树" - 因为你当然没有一棵树,你有一个有向图.

但是对于实际使用二叉树的传统"左右子树"实现的数据类型,则无法制作循环树(模数当然是使用反射或不安全代码的偷偷摸摸的技巧.)

Answer 2

如果你使用的是不可变数据结构,那么在严格(而不是懒惰)语言中,就不可能创建一个循环; 因为您必须按某种顺序创建元素,并且一旦创建了元素,您就不能将其变异以指向稍后创建的元素.因此,如果您创建了节点n,然后创建了指向n(可能是间接)的节点m,那么您永远无法通过使n指向m来完成循环,因为您不允许变异n,也不能指向n已指向的任何内容.

是的,你是正确的,你只能通过从叶子建立来创建一个不可变的树; 如果从根开始,则必须在创建根时修改根以指向其子项.只有从叶子开始,并创建每个节点指向其子节点,才能从不可变节点构造树.