Path: utzoo!utgpu!news-server.csri.toronto.edu!bonnie.concordia.ca!thunder.mcrcim.mcgill.edu!snorkelwacker.mit.edu!think.com!zaphod.mps.ohio-state.edu!usc!isi.edu!donc
From: donc@isi.edu (Don Cohen)
Newsgroups: comp.lang.lisp
Subject: Re: EQUAL on circular lists, yet again.
Message-ID: <18310@venera.isi.edu>
Date: 19 Jun 91 20:09:49 GMT
References: <FY.91Jun17160712@hardwick.lucid.com> <2867@prles2.prl.philips.nl>
Sender: news@isi.edu
Reply-To: donc@isi.edu (Don Cohen)
Organization: USC Information Sciences Institute
Lines: 26

It seems to me that the solution has to postulate a set of
equivalences.  Whenever you come across a non-list you can
potentially determine that the structures are not equivalent.
Otherwise you simply have to postulate that they are, and
check their cars and cdrs.  In order to avoid infinite
recursion, of course, any time that you come across a pair
that was already postulated equivalent, you don't recur.
The transitivity of equivalence can be used to reduce the
amount of checking.  The <angle brackets> below indicate
code to be filled in.

(defun equal-circle (x y &aux <equivalence-data>)
  (labels
   ((presume-equivalent (x y)
	<merge the equivalence classes of x and y>)
    (presumed-equivalent (x y)
	<determine whether the equivalence classes of x and y are the same>)
    (test-equivalent x y)
      (if (or (eq x y) (presumed-equivalent x y)) t
	(if (not (and (consp x) (consp y))) (return-from equal-circle nil)
	  (progn (presume-equivalent x y)
		 (test-equivalent (car x) (car y))
		 (test-equivalent (cdr x) (cdr y))))))
   (test-equivalent x y)))

There are pretty efficient ways of finding and merging equivalence classes.