Lean 4 (Meta)programming Cookbook

RBMap and RBTree🔗

Contributors: Anirudh Gupta

RBMap and RBTree are red-black trees used extensively throughout the Lean 4 compiler. Unlike HashMap, which requires a Hashable instance, these structures only require an ordering instance (Ord).

  1. RBMap (Red-Black Map)
  2. RBTree (Red-Black Tree)
  3. Application: Scheduling Processes with RBMap
  4. Application: Tracking Undefined Identifiers with RBTree