u/tikhonjelvisin r/haskell • Recommends
Radix Trees—How IntMap Works (Lambda World 2018)
0:00 / 0:00
Lambda World 2018 - The Radix Trees How IntMap Works - Tikhon Jelvis
Lambda World
10K subscribers • 16 videos on Hallway
- Recommended by 1 person: 1 in engineering communities.
- Presented by Tikhon Jelvis
Intermediate. Assumes working knowledge.
4.7K views7 years ago1 recommendation
Computer scienceProgramming languagesData structuresHaskell
Tikhon Jelvis explains the mechanics of Radix Trees and how Haskell implements them under the hood for the IntMap data structure.
This presentation by Tikhon Jelvis took place at Lambda World Seattle on September 18th, 2018 at the Living Computers Museum in Washington. The Radix Tree: How IntMap Works The Radix Tree (aka PATRICIA Trie) is an efficient data structure for key-value maps with integral keys. Radix tries come up in a wide range of applications like in-memory databases and the Linux kernel, and can be turned into a persistent data structure useful for functional code (Haskell's IntMap). With pictures and code, I'll walk you through how the data structure works, what Haskell's implementation looks like under the hood and several ways it's useful in functional code. I'll finish with a look towards the future: a quick overview of the Adaptive Radix Tree, a recently published variation on normal Radix Trees with real potential. While this talk will be Haskell flavored, the data structure itself and the general concepts are all language-agnostic. Follow: -twitter.com/lambda_world -twitter.com/47deg -twitter.com/tikhonjelvis Visit: -47deg.com/events for more details -lambda.worldWhy it's here
1 person recommends thisWhat people say. Recommended as a clear, visual explanation of Radix Trees and Haskell's IntMap implementation.
u/tikhonjelvisin r/haskell • Mentions
On “[RFC] Draft publication of `stm-trie`, a concurrent trie - comments/questions wanted”
I haven't looked at the code, so maybe I'm missing something obvious, but you can "compress" parts of the key that have no siblings into the corresponding node—that's what the PATRICIA trie that IntMap is based on does.
If you're curious, I have some pictures and code in this talk on adaptive radix trees (which are a cool generalization of PATRICIA tries, but in a way that is not super relevant here).