Back To Schedule
Saturday, November 17 • 11:40am - 12:20pm
Radix Trees: How IntMap Works

Sign up or log in to save this to your schedule, view media, leave feedback and see who's attending!

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.

avatar for Tikhon Jelvis

Tikhon Jelvis

Principal AI Scientist, Target
I picked up Haskell as my first functional language on a whim, and it's stuck with me ever since. I've worked with other functional languages too—a compiler in Racket, a backend service in OCaml—but now I'm back in the Haskell world, working on Target's supply chain optimization... Read More →

Saturday November 17, 2018 11:40am - 12:20pm PST