How can I instantiate immutable mutually recursive objects?

Question

I have an immutable recursive type:

public sealed class Foo { private readonly object something; private readonly Foo other; // might be null public Foo(object something, Foo other) { this.something = something; this.other = other; } public object Something { get { return something; } } public Foo Other { get { return other; } } } 

I need to create two objects of this type that relate to each other, i.e. a.Other == b && b.Other == a .

I do not want to abandon the invariance of immutability, because Foo intended to be used as a fly. I can (and I think should) refuse readonly in the fields and leave the "guts" mutable, but the open interface should be immutable.

Is popsicle immutability the only way to do this?

EDIT . I am trying to simulate a collection of types. Each type has a name and several attributes. Each attribute has a name and type. There are several mutually recursive types and that this problem arose there.

Answer 1

There are other ways to do this, but they may not have the properties you want.

Suppose you wanted to represent an immutable value tree constructed from leaves. It is pretty simple. You can have a node constructor that takes a value and a list of child nodes. This makes it quite easy to create new trees from old trees, and they are guaranteed to be acyclic.

Now suppose you want to represent an immutable oriented graph of values. Now you have a problem that nodes may have loops; there can be no “sheet” for plotting. The solution is to abandon the principle that node knows what its neighbors are. You can imagine an immutable graph by creating an immutable set of nodes and an immutable list of edges. To add a node to an immutable graph, you create a new graph with this node added to the node set. Similarly for adding edges; you create a new list of edges. Now the fact that there are cycles in the graph topology does not matter; no object has a loop in which objects it refers to.

Without knowing more about your actual problem space, it's hard to say which immutable data structure will work for your application. Can you tell us more about what you are trying to do?

I am trying to simulate a collection of types. Each type has a name and several attributes. Each attribute has a name and type. There are several mutually recursive types and that this problem arose there.

Well, you should have said that first. If there is one thing that I know of, it is type analysis. Obviously, the compiler must be able to handle all kinds of crazy type situations, including types with cyclic base classes, loops with internal types, type arguments, type restrictions, etc.

In the C # compiler, we solve these problems mainly by making objects "delivered" in their immutability. That is, when we first create a set of types, each type of object knows its name and its position in the source code (or metadata). Then the name becomes unchanged. Then we enable the base types and test them for loops; then the base types become immutable. Then we check for type constraints ... then we resolve the attributes ... and so on until everything is parsed.

I looked at other ways to do this. For example, we could use the same technique that I just proposed for graphs: create an immutable object, called, for example, "compilation", to which you can add types, thereby creating new immutable compilations. Compilation can track the "edges" between a type and its base type in an immutable hash map and then check the resulting graph for loops. The downside is that the type does not know its base type; you should ask compilation what the base type of a type is.

Here you can do the same. You can have a “set” class that contains a set of immutable types, and a multi-map from type to set of immutable attributes. You can create a set of types and a set of attributes as you like; the thing that changes is a map, not a type.

The downside of this is that you no longer request a type for your attributes; you are requesting a set for type attributes. This may not suit your needs if you need to pass types independently of any set.

Answer 2

It is definitely not possible to use a permanent write once. Let me explain why. You can set field values ​​only in the constructor. Therefore, if you want a refer to b , you need to pass a reference to the constructor of b to a . But b will be already frozen. So the only option is to instantiate b in constructor a . But this is not possible because you cannot pass a reference to a , because this not allowed inside the constructor.

From this point, the immutability of the Eskimos is the simplest and most elegant solution. Another way is to create a static Foo.CreatePair method that will instantiate two objects, cross-reference and return a frozen object.

 public sealed class Foo { private readonly object something; private Foo other; // might be null public Foo(object something, Foo other) { this.something = something; this.other = other; } public object Something { get { return something; } } public Foo Other { get { return other; } private set { other = value; } } public static CreatePair(object sa, object sb) { Foo a = new Foo(sa, null); Foo b = new Foo(sb, a); a.Other = b; return a; } } 

Answer 3

The following is an example of a Foo class with an immutable write once rather than immunity. A bit ugly but pretty basic. This is a proof of concept; You will need to customize it according to your needs.

 public sealed class Foo { private readonly string something; private readonly Foo other; // might be null public Foo(string s) { something = s; other = null; } public Foo(string s, Foo a) { something = s; other = a; } public Foo(string s, string s2) { something = s; other = new Foo(s2, this); } } 

Using:

 static void Main(string[] args) { Foo xy = new Foo("a", "b"); //Foo other = xy.GetOther(); //Some mechanism you use to get the 2nd object } 

Consider creating private constructors and creating a factory to create Foo pairs, as this is pretty ugly as it is written, and forces you to provide public access to others.

Answer 4

You can do this by adding a constructor overload that accepts the function, and passing the this reference to this function. Something like that:

 public sealed class Foo { private readonly object something; private readonly Foo other; public Foo(object something, Foo other) { this.something = something; this.other = other; } public Foo(object something, Func<Foo, Foo> makeOther) { this.something = something; this.other = makeOther(this); } public object Something { get { return something; } } public Foo Other { get { return other; } } } static void Main(string[] args) { var foo = new Foo(1, x => new Foo(2, x)); //mutually recursive objects Console.WriteLine(foo.Something); //1 Console.WriteLine(foo.Other.Something); //2 Console.WriteLine(foo.Other.Other == foo); //True Console.ReadLine(); }