Hashing Modulo Alpha Equivalence

Explore a groundbreaking technique for efficient hashing modulo alpha-equivalence in this conference talk from YOW! 2021. Delve into Simon Peyton Jones' innovative approach to identifying identical subtrees in program syntax trees, robust to alpha-renaming. Learn about the key insight of using a weak, commutative hash combiner to achieve O(n*(log n)^2) time complexity while maintaining low collision probability. Gain valuable insights into functional programming, Haskell, and the Glasgow Haskell Compiler (GHC) from one of the field's leading experts. Discover how this method can revolutionize program analysis and optimization in various applications.

Hashing Modulo Alpha Equivalence • Simon Peyton Jones • YOW! 2021