DESIGNING DATA STRUCTURES FOR THE TYPELEVEL ECOSYSTEM
summary
radixtree is a small generic library (targets cats typeclasses) that implements a single-node radix tree optimized for strings, with typeclass constraints on methods not constructors, and fast operations: filter by prefix, merge, and add-via-merge. it uses internal mutable arrays for compactness and structural sharing so equality is structural and fast. packing reduces memory by about 5× on an English word list and 7.7× on a large German corpus. code is on GitHub, works for the author’s use cases but is not a drop-in replacement for Scala collections.
AI-written summary · about
chapters (9)
- 0:00Radix trees introduction
- 3:17Radix tree advantages
- 10:04Publishing on GitHub
- 13:12Suffix packing memory
- 17:49German words efficiency
- 20:43Organizing typeclass libraries
- 24:30Essential type classes
- 27:45Dependencies and testing
- 30:16Performance vs completeness
related talks
39mExtreme Cleverness: Functional Data Structures in Scala
31mRadix Trees: How IntMap Works
40mADTs For The Win!
28mRust and Scala, Sitting in a Tree….
32mLIFTING DATA STRUCTURES TO THE TYPE-LEVEL
35mIntroducing Typelevel Scala into an OO environment
42mWhat Scala can learn from Rust, Swift, and C++
45mTypelevel Programming 101: The Subspace of Scala