This article introduces 'thinnings' as mathematical objects that witness sublist relationships, visualizable as non-overlapping strings between slots. They can be represented as boolean lists and serve as bulk operations for de Bruijn index shifting, similar to how permutations consolidate swaps. The author finds them particularly useful for lambda egraphs and generalized union-find operations.
Background
Thinnings are mathematical objects that serve as witnesses to sublist relationships, previously seen mainly in dependent type theory contexts but applicable to any programming language. They provide a way to bulk-process de Bruijn index shifting operations.
- Source
- Lobsters
- Published
- Mar 9, 2026 at 11:19 AM
- Score
- 7.0 / 10