Extreme Cleverness: Functional Data Structure in Scala
From the description:
Daniel Spiewak shows how to create immutable data that supports structural sharing, such as: Singly-linked List, Banker’s Queue, 2-3 Finger Tree, Red-Black Tree, Patricia Trie, Bitmapped Vector Trie.
Every now and again I see a presentation that is head and shoulders above even very good presentations. This is one of those.
The coverage of the Bitmapped Vector Trie merits your close attention. Amazing performance characteristics.
Satisfy yourself, see: http://github.com/djspiewak/extreme-cleverness