Skip to main content

Posts

Showing posts from April, 2012

Immutable Hash Array Mapped Trie in C#

I just completed an implementation of an immutable hash array mapped trie (HAMT) in C#. The HAMT is an ingenious hash tree first described by Phil Bagwell. It's used in many different domains because of its time and space efficiency, although only some languages use the immutable variant. For instance, Clojure uses immutable HAMTs to implement arrays/vectors which are essential to its concurrency.The linked implementation is pretty much the bare minimum supporting add, remove and lookup operations, so if you're interested in learning more about it, it's a good starting point. Many thanks also to krukow's fine article which helped me quickly grasp the bit-twiddling needed for the HAMT. The tree interface is basically this:/// <summary> /// An immutable hash-array mapped trie. /// </summary> /// <typeparam name="K">The type of keys.</typeparam> /// <typeparam name="T">The type of values.</typeparam> public class Tre…