Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!think.com!spool.mu.edu!uunet!mcsun!hp4nl!phigate!prle!prles2!apolloway.prl.philips.nl
From: kostelij@apolloway.prl.philips.nl (T. Kostelijk 43897)
Newsgroups: comp.lang.lisp
Subject: EQUAL on circular lists
Message-ID: <2849@prles2.prl.philips.nl>
Date: 5 Jun 91 14:08:48 GMT
Article-I.D.: prles2.2849
Sender: news@prles2.prl.philips.nl
Organization: none
Lines: 46

Subject: EQUAL on circular lists

The function EQUAL may not terminate when two non-eq trees of conses
are circular. For example:

(setf p         (cons 'a nil) 
      (cdr p)   p
      q         (cons 'a nil)
      (cdr q)   q)

Now both p and q look alike, but (equal p q) won't terminate.
The (standard) printed representation of both p and q is

 (a a a ..<etc>.. )
 

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?


TESTCASE:

As a simple testcase, both p and q are also "EQUAL" to r, which is defined by:

(setf r          (list a a a a)
      (cddddr r) (cdr r))


Other examples:    v and w are "EQUAL"

(setf v         '(a nil)
      (cadr v)  v
      w         '(a (a nil))
      (cdadr w) w)



FROM:

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