Efficient Nondestructive Equality Checking for Trees and Graphs

Michael D. Adams and R. Kent Dybvig

Status: Published

Abstract

The Revised6 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.

Keywords

equality, union-find, DFA equivalence, eq hash tables, Scheme

Citation

Michael D. Adams and R. Kent Dybvig. 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.

BibTeX Entry

@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},
}

Copyright Notice

© ACM, 2008. This is the author’s version of the work. It is posted here by permission of ACM for your personal use. Not for redistribution. The definitive version was published in ICFP ’08: Proceeding of the 13th ACM SIGPLAN international conference on Functional programming, (2008). http://doi.acm.org/10.1145/1411204.1411230.