Reading through some of Stylish Haskell's dependencies, and the hashmap code seems really weird...

Part of it is that Haskell's datamodel prefers tree-based collections rather than array-based ones, but it seems like more than that. I'll figure it out...

O.K., they do have a file explaining the weirdness:

They explain that they're implementing a variant called "hash array mapped trie", which basically is a trie indexed by the key's hash.

@alcinnz You've probably figured this out already, but to be explicit: The reason why Haskell data structures often avoid array-based implementations is because Haskell likes immutability. E.g., inserting an element in a map goes like this:

new_map = M.insert old_map key val

That conceptually creates copy of the entire data structure, since old_map is still accessible. If it was implemented as a naive hash table (i.e. based on an array), then the implementation would be forced to create a full copy. With trees, only the nodes that have been changed need to be copied, which is much more efficient.

Sign in to participate in the conversation

For people who care about, support, or build Free, Libre, and Open Source Software (FLOSS).