A persistent map is an immutable key-value collection: an update returns a new map while leaving earlier versions available. In .NET, ImmutableDictionary supplies this structure. It can represent graph adjacency, where each node maps to its adjacent nodes. section 8.2
When a map from each key to multiple values is needed, wrap an ImmutableDictionary whose values are immutable sets. Add and remove update the associated set; lookup checks whether a key contains a value. The stated add, remove, and lookup operations are O(1). section 8.2
Listing 8.1 Implementing a multidictionary by wrapping a regular dictionary
readonly struct ImMulti<K, V> where K : notnull where V : notnull
{
private readonly ImmutableDictionary<K, ImmutableHashSet<V>> dict;
public static ImMulti<K, V> Empty =
new(ImmutableDictionary<K, ImmutableHashSet<V>>.Empty);
private ImMulti(ImmutableDictionary<K, ImmutableHashSet<V>> dict) =>
this.dict = dict;
public bool IsEmpty => dict.IsEmpty;
public bool ContainsKey(K k) => dict.ContainsKey(k);
public bool HasValue(K k, V v) =>
dict.ContainsKey(k) && dict[k].Contains(v);
public IEnumerable<K> Keys => dict.Keys;
public ImmutableHashSet<V> this[K k] => dict[k];
public ImMulti<K, V> SetItem(K k, ImmutableHashSet<V> vs) =>
new(dict.SetItem(k, vs));
public ImMulti<K, V> SetSingle(K k, V v) =>
dict.SetItem(k, ImmutableHashSet<V>.Empty.Add(v));
public ImMulti<K, V> SetEmpty(K k) =>
dict.SetItem(k, ImmutableHashSet<V>.Empty);
public ImMulti<K, V> Add(K k, V v) =>
ContainsKey(k) ?
new(dict.SetItem(k, dict[k].Add(v))) :
SetSingle(k, v);
public ImMulti<K, V> Remove(K k) => new(dict.Remove(k));
public ImMulti<K, V> Remove(K k, V v) =>
new(dict.SetItem(k, dict[k].Remove(v)));
}
This C# listing implements a multivalue map by wrapping ImmutableDictionary<K, ImmutableHashSet<V>>. section 8.2
