Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Generating immutable cyclic data structures

Suppose I have this simple class:

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

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

It would be impossible to generate a cyclic graph of pairs.

How would you create a similar class, that is still immutable, but can be used somehow to generate cyclic graphs?

like image 296
configurator Avatar asked Oct 24 '10 03:10

configurator


People also ask

What is an example of an immutable data structure?

Immutable data structure are data structures, like lists, arrays, sets etc., which cannot be changed, meaning that the values inside them can't be added, removed, moved or swapped. Instead of changing the data structure you make a new version of the data structure which is a separate value.

What is a cyclic data structures?

If you imagine the members of the data structure laid out as a graph, a cyclic data structure is where a member refers back to another one or the structure itself. For example: var obj = new Object(); obj.

Why is data structure immutable?

Immutable data structures provides referential transparency which makes it easier to reason about our program locally. Another way to think about it is that every time we execute a pure (referentially transparent) function with the same input, we get the same output.

Are immutable data structures faster?

@elysium: Immutable data structures are generally not competitively performant compared to their mutable counterparts, particularly in the context of parallelism because they incur many more allocations and cache misses.


1 Answers

There are zillions of ways to represent graph structures. One such way is with a matrix. each row and column is indexed by the vertex, and each cell in the matrix represents a directed (possibly weighted) edge. A simple, cyclic graph, with 0's as no connecting edge and 1 with a connecting edge would just be like so:

| 0 1 |
| 1 0 |

As with many immutable structures, the way you construct them is by returning new structures based on the desired relationship of given matrices. for instance, if we wanted to take the above graph and add an edge on the first vertex back onto itself, the matrix representing that is just.

| 1 0 |
| 0 0 |

and to combine that with the other matrix, we just add them together.

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

Of course, there are many ways to represent matrices, with different tradeoffs for speed, space, and certain other operations, but that's a different question.

like image 142
SingleNegationElimination Avatar answered Nov 08 '22 19:11

SingleNegationElimination