Is there an open source immutable dictionary for C#, with fast 'With/Without' methods?

Question

I'm looking for a proper C# immutable dictionary, with fast update methods (that create a partial copy of the dictionary with slight changes). I've implemented one myself, using zippers to update a red-black tree, but it's not particularly fast.

By 'immutable dictionary' I don't just mean readonly or const. I want something that has reasonably fast 'With' and 'Without', or equivalent, methods that return a thing with slight modifications without modifying the original.

An example from another language is map in Scala

Answer 1

There is some implementation of the immutable dictionary based on read-only binary AVL tree.

/**
 * To modify, use the InsertIntoNew and RemoveFromNew methods
 * which return a new instance with minimal changes (about Log C),
 * so this is an efficient way to make changes without having
 * to copy the entire data structure.
 */

Please take a look at the InsertIntoNew() method:

/** Return a new tree with the key-value pair inserted
 * If the key is already present, it replaces the value
 * This operation is O(Log N) where N is the number of keys
 */
public ImmutableDictionary<K,V> InsertIntoNew(K key, V val)
{ ... }

The RemoveFromNew() method:

/** Try to remove the key, and return the resulting Dict
 * if the key is not found, old_node is Empty, else old_node is the Dict
 * with matching Key
 */
public ImmutableDictionary<K,V> RemoveFromNew(K key, out ImmutableDictionary<K,V> old_node)
{ ... }

Also, there is another implementation: Immutable AVL Tree in C#. It has the same O(log N) lookup and insertion times.

Additional references

• Seems to be a mirror: brunet/ImmutableDictionary.cs at master · johnynek/brunet · GitHub.
• Seems to be similar: ImmutableCollections/ImmutableDictionary.cs at master · mono/ImmutableCollections · GitHub.