From ...
From: Erik Naggum <erik@naggum.no>
Subject: Re: Deep copy in lisp: how?
Date: 2000/04/10
Message-ID: <3164356890914970@naggum.no>#1/1
X-Deja-AN: 609079759
References: <38F0B90A.8FC4B502@san.rr.com> <3164291289641126@naggum.no> <u766tqpam2.fsf@o2-3.ebi.ac.uk>
mail-copies-to: never
Content-Type: text/plain; charset=us-ascii
X-Complaints-To: newsmaster@eunet.no
X-Trace: oslo-nntp.eunet.no 955370441 14565 195.0.192.66 (10 Apr 2000 12:40:41 GMT)
Organization: Naggum Software; vox: +47 8800 8879; fax: +47 8800 8601; http://www.naggum.no
User-Agent: Gnus/5.0803 (Gnus v5.8.3) Emacs/20.5
Mime-Version: 1.0
NNTP-Posting-Date: 10 Apr 2000 12:40:41 GMT
Newsgroups: comp.lang.lisp

* Philip Lijnzaad <lijnzaad@ebi.ac.uk>
| On 09 Apr 2000 17:48:09 +0000, 
| "Erik" == Erik Naggum <erik@naggum.no> writes:
| 
| Erik> implementing a mechanism that avoids descending into cyclic structures is
| Erik> amazingly easy.  
| 
| if slightly non-obvious at first. For those confused, you have two parts of
| your function step through the elements of a list, one going in single steps,
| the other in steps of two. If they ever end up in the same element, the list
| must have been circular.
| 
| Erik> detection is easy with the rabbit and the hare algorithm.
| 
| Is this an optimized version of the tortoise and the hare algorithm? 

  yes (my silly mistake).  you just described it in the above paragraph, so
  you must know it under a different name, but the key is to realize that
  it only _detects_ a circularity, after it has happened -- there is no
  guarantee that you find the first such element.

#;Erik