Radix Trees: How IntMap Works

The Radix Tree (aka PATRICIA Trie) is an efficient data structure for key-value maps with integral keys. Used in a range of applications (including the Linux kernel), the Radix Tree is particularly relevant to functional programmers because it has an efficient persistent version for use in purely functional code. Haskell's widely used IntMap type is a Radix Tree under the hood. With code and diagrams, I'll walk you through how Radix Trees work, what properties they have and how they can be used effectively. I'll finish with a look towards the future and the Adaptive Radix Tree, a recently published variation on the normal Radix Tree with some real potential. While the code for this talk will be Haskell-flavored, the ideas are language-agnostic.