Editing Trees with Zippers
summary
Zippers let code traverse and mutate recursive trees without destructive updates by keeping a focus plus a context and implementing most moves as constant time pointer rearrangements, with the notable cost that O(1) operations except go-up which is O(n); improvement comes from changing the tree representation (scars, tripartite sections) or using indexed collections. Examples include a Scala implementation, uses in file systems and tiling window managers, and searcy JSON cursors using vectors for indices that keep original JSON immutable while enabling efficient edits.
AI-written summary · about
chapters (26)
- 0:00Introduction
- 0:56What is Zipper
- 1:08What is Traverse
- 1:30Traverse Mutation
- 2:13Recursive
- 3:15Tree
- 4:37Subtree
- 4:57Zipper
- 5:26Zipper Scala
- 10:32Zipper FlatMap
- 11:15Insert Down
- 12:20Insert Left
- 12:37Insert Right
- 13:54Change
- 14:20Go Up
- 15:29Section
- 16:22Use Cases
- 17:48JSON Zippers
- 18:02Cursors
- 19:05Zipper with Focus
- 19:50Indexed Collections
- 24:17Traversal Mutation
- 25:04Derivative of Data Type
- 25:40Remove Recursion
- 28:43Visual Representation
- 29:36Conclusion
related talks
12mThey're functional! They're efficient!!
56mEditing the World with React and Zettel
25mWhen all the nails are trees, the hammer you need probably looks like a chainsaw
34mImmutability: Putting The Dream Machine To Work
46mIncremental, zero-config Code Nav using stack graphs
27mFrom Zero to Binary Search Tree
19mChange Detection Reinvented
41mmobx-state-tree, stop getting into all those states!