skip to main content
10.1145/1411204.1411230acmconferencesArticle/Chapter ViewAbstractPublication PagesicfpConference Proceedingsconference-collections
research-article

Efficient nondestructive equality checking for trees and graphs

Published: 20 September 2008 Publication History

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.

Supplementary Material

JPG File (1411230.jpg)
index.html (index.html)
Slides from the presentation
ZIP File (p179-slides.zip)
Supplemental material for: Efficient nondestructive equality checking for trees and graphs
Audio only (1411230.mp3)
Video (1411230.mp4)

References

[1]
William D. Clinger. SRFI 85: Recursive equivalence predicates, March 2006. URL http://srfi.schemers.org/srfi-85/.
[2]
William D. Clinger. SRFI 85: Recursive equivalence predicates (corrected reference implementation), December 2007. URL http://srfi.schemers.org/srfi-85/post-mail-archive/msg00001.html.
[3]
Zvi Galil and Giuseppe F. Italiano. Data structures and algorithms for disjoint set union problems. ACM Comput. Surv., 23(3):319--344, 1991. ISSN 0360-0300.
[4]
Benrard A. Galler and Michael J. Fisher. An improved equivalence algorithm. Commun. ACM, 7(5):301--303, 1964. ISSN 0001-0782.
[5]
Abdulaziz Ghuloum and R. Kent Dybvig. Generation-friendly eq hash tables. In 2007 Workshop on Scheme and Functional Programming, pages 27--35, 2007. URL http://sfp2007.ift.ulaval.ca/programme.html.
[6]
John E. Hopcroft and R. M. Karp. A linear algorithm for testing equivalence of finite automata. Technical Report 71-114, Cornell University, Ithaca, NY, 1971. URL http://ecommons.library.cornell.edu/handle/1813/5958.
[7]
Richard Kelsey, William Clinger, and Jonathan Rees (eds.). Revised5 report on the algorithmic language Scheme. Higher-Order and Symbolic Computation, 11(1):7--105, 1998. Also appears in ACM SIGPLAN Notices 33(9), September 1998.
[8]
Michael Sperber, R. Kent Dybvig, Matthew Flatt, and Anton van Straaten (eds.). Revised6 report on the algorithmic language Scheme, September 2007. URL http://www.r6rs.org/.
[9]
Robert E. Tarjan and Jan van Leeuwen. Worst-case analysis of set union algorithms. J. ACM, 31(2):245--281, 1984. ISSN 0004-5411.
[10]
Robert Endre Tarjan. Efficiency of a good but not linear set union algorithm. J. ACM, 22(2):215--225, 1975. ISSN 0004-5411.

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences
ICFP '08: Proceedings of the 13th ACM SIGPLAN international conference on Functional programming
September 2008
422 pages
ISBN:9781595939197
DOI:10.1145/1411204
  • cover image ACM SIGPLAN Notices
    ACM SIGPLAN Notices  Volume 43, Issue 9
    ICFP '08
    September 2008
    399 pages
    ISSN:0362-1340
    EISSN:1558-1160
    DOI:10.1145/1411203
    Issue’s Table of Contents
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 20 September 2008

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. dfa equivalence
  2. eq hash tables
  3. equality
  4. scheme
  5. union-find

Qualifiers

  • Research-article

Conference

ICFP08
Sponsor:

Acceptance Rates

Overall Acceptance Rate 333 of 1,064 submissions, 31%

Upcoming Conference

ICFP '25
ACM SIGPLAN International Conference on Functional Programming
October 12 - 18, 2025
Singapore , Singapore

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • 0
    Total Citations
  • 423
    Total Downloads
  • Downloads (Last 12 months)0
  • Downloads (Last 6 weeks)0
Reflects downloads up to 18 Feb 2025

Other Metrics

Citations

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media