[DanWaterworth]

The Haskell unordered-containers package also uses HAMTs.

This technique of increasing the node size in order to speed up traversals on conventional architectures is actually quite general. You could do the same thing to finger-trees for example. One disadvantage is that lots of different versions of the same structure take up more space than they would otherwise.

An advantage of applying tree-broadening to a finger-tree rather than a generic balanced tree structure, is that, depending on the ordering, it may make in order traversal faster, because elements that are near each other in the structure are also (in some sense) close together in memory.

[weareconvo]

You mean to tell me that even in the Functional Programming world, there are still tradeoffs between memory and performance to consider?

[fusiongyro]

I'm not sure where you would have gotten the idea that there wouldn't be. By and large, we tend to be more interested in correctness than performance, but that doesn't mean we aren't interested in performance.