Génération des structures de données cycliques immuables

Question

Supposons que j'ai cette classe simple:

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

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

Il serait impossible de générer un graphique cyclique de paires.

Comment créeriez-vous une classe similaire, qui est encore immuable, mais qui peut être utilisée d'une manière ou d'une autre pour générer des graphiques cycliques?

Answer 1

Je ne pense pas que ce soit possible avec une classe strictement immuable du type que vous avez proposé. La seule chose que je peux penser est d'ajouter une propriété avec un setter qui vérifie si un champ est nul, et lui permet d'être défini si c'est le cas. De cette façon, vous pouvez laisser le champ first dans le premier objet null, et une fois que vous avez créé le dernier objet du cycle, définissez ce champ de façon appropriée pour fermer la boucle. Une fois qu'il est défini, il n'est plus nul, et le setter ne permet plus de le modifier. Il serait encore possible que le champ soit changé par un code interne à la classe, bien sûr, mais il serait essentiellement immuable de l'extérieur.

Quelque chose comme ça (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 
} 

Answer 2

Il y a des millions de façons de représenter des structures de graphes. Un tel moyen est avec une matrice. chaque ligne et colonne est indexée par le sommet, et chaque cellule de la matrice représente un bord dirigé (éventuellement pondéré). Un simple, graphique cyclique, avec des 0 comme aucun bord de liaison et 1 avec un bord de liaison serait tout simplement comme ceci:

| 0 1 | 
| 1 0 | 

Comme de nombreuses structures immuables, la façon dont vous les construire est en retour de nouvelles structures sur la base relation désirée des matrices données. par exemple, si nous voulions prendre le graphe ci-dessus et ajouter un arête sur le premier sommet sur lui-même, la matrice représentant cela est juste.

| 1 0 | 
| 0 0 | 

et de combiner cela avec l'autre matrice, nous les ajoutons simplement ensemble.

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

Bien sûr, il y a plusieurs façons de représenter des matrices, avec des compromis pour la vitesse, l'espace, et certaines autres opérations, mais c'est une autre question.

Answer 3

Je prendrais une approche fonctionnelle, en passant une continuation dans le ctor. Alternativement, il pourrait prendre une séquence d'éléments similaires à la place (penser IEnumerable comme argument).