[jasonwatkinspdx]

A more common name is Array Mapped Trie. See the papers by Phil Bagwell (RIP). DJB's crit-bit Trie page is good also. Many people forget that it's rather easy to pack tries for locality since there is no rebalancing to fragment nodes.

AMT's are one of clojure's most heavily used container types.

[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.

[snprbob86]

Tries are basically just sorted prefix trees, and you're right, they form the basis of sorted maps and sets in Clojure. However, Clojure also has https://github.com/clojure/data.finger-tree for cases where tries don't make sense: namely, double-ended queues (amortized constant time push and pop from both ends) and sorted sets with log-n index access.