Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!think.com!sdd.hp.com!wuarchive!uunet!mcsun!hp4nl!phigate!prle!prles2!apolloway.prl.philips.nl
From: kostelij@apolloway.prl.philips.nl (T. Kostelijk 43897)
Newsgroups: comp.lang.lisp
Subject: RE: EQUAL on circular lists
Message-ID: <2867@prles2.prl.philips.nl>
Date: 13 Jun 91 14:54:55 GMT
Sender: news@prles2.prl.philips.nl
Organization: none
Lines: 83

Subject: EQUAL on circular lists

> kostelij@apolloway.prl.philips.nl's message of 5 Jun 91 14:08:48 GMT

> QUESTION:
> 
> Does anyone have an extended version of EQUAL which can determine in 
> finite time whether two trees of conses have the same printed
> (possibly infinite) representation?
>

The reactions I received confirmed me that not only novice Lispers read rn, 
and that it is useful for exchanging information about common problems.

A short answer to reactions received on the above question, that might be
of general use.

Frank Yellin (uunet!stanford.edu!lucid.com!karoshi!fy) asked 
for a more formal specification. 


MORE FORMAL DEFINITION OF EQUAL-CIRCLE:

Consider the infinite set S of functions denoted as C{A|D}*R,
and without loss of generality, only consider (possibly circular) lists and symbols.
Any two objects a and b are defined EQUAL-CIRCLE iff the following holds:
  for every function f in S for which (f a) is 
    a. a symbol,  1. (f b) is a symbol and
                  2. (eql (f a) (f b)),
    b. a cons,    1. (f b) is a cons,
    c. not defined (an error), (f b) must be not defined.

Notes: 1. Ofcourse I know that only a few functions of S are usually implemented,
          but that is irrelevant for formal statements.
       2. The definition could be extended easily to other atoms than symbols.
       3. (to Frank) So now obviously the lists (#1=(a . #1) b) and (#1=(a . #1) c)
          are not EQUAL-CIRCLE, take f = CADR


DETERMINISTIC FINITE STATE AUTOMATA:

Frank also confirmed my own impression that the problem seems pretty
much the same as the problem of determining whether two deterministic
finite state automata are equivalent.
This problem has a worst case complexity of sizeof(a) * sizeof(b),
where 'size' is the number of cons cells and atoms in the object.

Perhaps someone has a proof of the FSA statement?


THE BEST ALGORTIHM:

The algorithm I like most was send in by Bernhard Pfahringer
(bernhard@ai-vie.uucp), from Vienna, by using the trick to make conses 
EQ temporarily, thus preventing EQUAL-CIRCLE from going into endless loops.
It has the following definition:

(defun EQUAL-CIRCLE (cons1 cons2)
  "Equal-circle determines equivalence between possibly circular trees"
  (or (eql cons1 cons2)
      (and (consp cons1)
	   (consp cons2)
	   (let ((f2 (first cons2))
		 (r2 (rest cons2)))
	     (unwind-protect
		  (progn (setf (first cons2) (first cons1) ; trick
			       (rest cons2) (rest cons1))      
			 (and (equal-circle (first cons1) f2)
			      (equal-circle (rest cons1) r2)))
	       (setf (first cons2) f2                      ; untrick
		     (rest cons2) r2))))))

It works quite efficiently for usual cases and is not hard to understand.     
The runtime can be reduced up to 50% by leaving the UNWIND-PROTECT out,
but then the process should not be interrupted for data consistency.

I want to thank for all reactions, especially from Bernhard and Frank.


FROM:

Ton Kostelijk, 
email adress: kostelij@apolloway.prl.philips.nl