ImplementationDetails

Right now, the implementation focuses on providing very robust and reasonably efficient immutable maps (as well as their degenerated case, sets) and implements a few other helper data structures as a side effect. Eventually I'd like to provide a full-fledged library of immutable data structures.

The immutable map is implemented as an hash array mapped trie. Most of operations that can be implemented efficiently on top of HAMTs are provided, with the notable exception of hashCode, which is not implemented at all right now. In particular, computing the union and intersection of two maps is reasonably fast, which is not the case in the Scala and Clojure implementations AFAIK, but I have found myself using this operation a lot in practice.

The code is basically a port of an included reference Haskell implementation I wrote to help me grok the details of the datastructure, and of a set of quickcheck tests that induce a 100% code coverage.

The tests compare each method against its naive implementations on a lot of different inputs thanks to propcheck.