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