Efficient nondestructive equality checking for trees and graphs

Michael D. Adams and R. Kent Dybvig

The 13th ACM SIGPLAN International Conference on Functional Programming (ICFP 2008)
Victoria, British Columbia, Canada, September 22-24, 2008

---

Abstract

The Revised^6 Report on Scheme changed the semantics of equal? so that it is now required to terminate even on cyclic inputs. While there are a number of methods for implementing this by using DFA equivalence or union-find algorithms, these methods may impose unacceptably large overheads for small acyclic inputs in which they are not actually needed.

This paper presents an implementation of equal? that performs well on a wide range of inputs both large and small, cyclic and acyclic by incurring most of the overhead only when necessary. The algorithm is presented as a sequence of incremental improvements to the straightforward implementation of equal? that works only for acyclic inputs. The final result is an implementation that guarantees termination while never being more than a small factor slower than whichever of the acyclic or union-find algorithms would have been fastest.

---

START Conference Manager (V2.54.6)