Please log in to watch this conference skillscast.
In many applications, one wants to identify identical subtrees of a program syntax tree. This identification should ideally be robust to alpha-renaming of the program, but no existing technique has been shown to achieve this with good efficiency (better than O(n^2) in expression size). We present a new, asymptotically efficient way to hash modulo alpha-equivalence. A key insight of our method is to use a weak (commutative) hash combiner at exactly one point in the construction, which admits an algorithm with O(n*(log n)^2) time complexity. We prove that the use of the commutative combiner nevertheless yields a strong hash with low collision probability.
YOU MAY ALSO LIKE:
- The Launch of the Haskell Foundation (SkillsCast recorded in November 2020)
- Haskell eXchange 2021 (Online Conference on 16th - 17th November 2021)
- Abstract Fun-sense: a functional perspective on life (SkillsCast recorded in May 2021)
- Eliminating Bugs with Dependently Typed Haskell (SkillsCast recorded in May 2021)