The Revised<sup>6</sup> Report on Scheme requires its generic equivalence predicate, equal?, to terminate even on cyclic inputs. While the terminating equal? can be implemented via a DFA-equivalence or union-find algorithm, these algorithms usually require an additional pointer to be stored in each object, are not suitable for multithreaded code due to their destructive nature, and may be unacceptably slow for the small acyclic values that are the most likely inputs to the predicate.
This paper presents a variant of the union-find algorithm for equal? that addresses these issues. It performs well on large and small, cyclic and acyclic inputs by interleaving a low-overhead algorithm that terminates only for acyclic inputs with a more general algorithm that handles cyclic inputs. The algorithm terminates for all inputs while never being more than a small factor slower than whichever of the acyclic or union-find algorithms would have been faster. Several intermediate algorithms are also presented, each of which might be suitable for use in a particular application, though only the final algorithm is suitable for use in a library procedure, like equal?, that must work acceptably well for all inputs.
equality, union-find, DFA equivalence, eq hash tables, Scheme
and . Efficient nondestructive equality checking for trees and graphs. In ICFP ’08: Proceeding of the 13th ACM SIGPLAN international conference on Functional programming, pages 179–188. ACM, New York, NY, USA, 2008. ISBN 978-1-59593-919-7. doi: 10.1145/1411204.1411230.
@inproceedings{adams2008efficient,
author = {Adams, Michael D. and Dybvig, R. Kent},
title = {Efficient Nondestructive Equality Checking for Trees and Graphs},
booktitle = {ICFP '08: Proceeding of the 13th ACM SIGPLAN international conference on Functional programming},
pages = {179--188},
year = {2008},
address = {New York, NY, USA},
publisher = {ACM},
isbn = {978-1-59593-919-7},
doi = {10.1145/1411204.1411230},
}