An Efficient Functional Map
Balanced Binary Search Trees
- update creates a new path (copying only log(n) nodes)
- lookup and update in log(n)
- worst-case guaranteed by balancing
- rebalancing can also be done functionally on update
Alternative:
- hash table with an update log
- constant-time access for last version produced in computation
- internally mutable, observationally immutable!