Dec 30, 2017

I did some work on making Array Mapped Tries cache efficient here: https://sinusoid.es/misc/immer/immer-icfp17.pdf

I am also exploring Hash Array Mapped Tries. CHAMP is a good start at making them cache efficient: https://michael.steindorfer.name/publications/oopsla15.pdf

I agree that the complexity of implementing these data-structures is annoying.

One interesting insight though is that Array Mapped Tried addressing works mostly like page table hierarchies for virtual memory addressing. I think there is a lot of value in providing Array Mapped Trie based core construct at language runtime level.

It is not an easy data-structured to be programmed ad-hoc. Clojure did a huge service to the world by using these as their default data-structure and showing their value to the world, all with a convenient and nice syntax. I think there is interesting new oportinities and research lines to use them at other levels between the OS and language runtime for concurrency and immutability centric languages...

Aug 14, 2017

This paper was published back in 2015: https://michael.steindorfer.name/publications/oopsla15.pdf

I wonder why the improvement wasn't adopted yet by the Clojure and Scala communities.