Subject: Re: Deep copy in lisp: how?
From: Erik Naggum <erik@naggum.no>
Date: 2000/04/10
Newsgroups: comp.lang.lisp
Message-ID: <3164356890914970@naggum.no>

* 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