C# library that implements persistent array, double linked list, dictionary and more

| Package with interfaces | | | Package with implementation | |

The fundamental benefit of persistence is that it makes it significantly easier to reason about how the code works, enabling you to quickly write correct and elegant code. Consider a single-threaded program. At a given line of code, you may be wondering about the state of an persistent collection. You can easily determine that by locating those locations in code where the collection was created. There’s usually only one or few such locations. By continuing this process, you’ll get to either a mutable source or the empty collection. It doesn’t matter if the immutable collection has been passed to methods because its structure is guaranteed to be preserved, so you don’t have to consider what happens in those methods. The main goal of persistent data structures is to write efficient code free from side effects.

List has O(1) random access complexity, path-copying and tail optimiztion.

var listA = new PersistentList<int>();
var listB = listA.Add(15);
var e = listB[0];
Debug.Assert(e == 15);
var listC = listB.Set(0, 33);
Debug.Assert(listB[0] == 15);
Debug.Assert(listC[0] == 33);

Dictionary built using PersistentList.

var dictA = new PersistentDictionary<int, string>();
var dictB = dictA.Set(15, "B");
var dictC = dictA.Set(15, "C");
Debug.Assert(dictB[15] != dictC[15]);
var dictD = dictC.SetItems(new[]{new KeyValuePair<int, string>(15, "D"), new KeyValuePair<int, string>(87, "A")});
Debug.Assert(dictD.Count == 2);

Hash set is also built using PersistentList.

var setA = new PersistentSet<string>();
var setB = setA.Add("aadad");
var setC = setB.Add("Cadada");
Debug.Assert(setC.Count == 2);
var setD = setC.Clear();
Debug.Assert(setC.Count == 2);
Debug.Assert(setD.IsEmpty);

PersistentLinkedList uses both path-copying and fat-node approaches to optimize version access and new version creation.

var llA = new PersistentLinkedList<int>();
var llB = llA.AddLast(15);
var llC = llB.AddFirst(71);
Debug.Assert(llB.First != llC.FirstOrDefault());
var llD = llC.Insert(1, 1000);
Debug.Assert(llD.First == llC.First && llD.Last == llC.Last);

Simple yet efficient way if we need only one side of collection.

var stackA = new PersistentStack<char>();
var stackB = stackA.Push('a');
Debug.Assert(stackA.IsEmpty);
var stackC = stackB.Push('d');
Debug.Assert(stackC.Peek() == 'd' && stackB.Peek() == 'a');

All examples can be found in PDS.Playground project.

All collections also have implementation of undo-redo mechanic to rollback changes:

• Undo returns us to state before last modifying operation.
• Redo returns us to state before last undo.
• Any modifying operation clears redo stack.

Official stands for System.Collections.Immutable
Tunnel is ImmutableTreeList from this project
Atropos is previous year nsu course project
Pds is this project

First test is adding range of elements into the empty collection. Memory allocation during test:

Second test is same adding, but this time we enforces collections to add items one by one. Memory allocation during test:

• Andrey Pleshkov
• Artyom Lyamin