Re: can s-exprs represent a graph without eval?

[Lieven Marchand <address@hidden>]

Geoffrey Knauth <geoff@knauth.org> writes:

> I've never seen this, it's certainly interesting, but how to you
> detect that you're just going around in circles?
> 
> (Let's say someone passes you v and you aren't suspecting v has this
> structure.)

Common Lisp has a standard function LIST-LENGTH that returns nil for a
circular list and the length for a proper list.

LIST-LENGTH can obviously be implemented by keeping the addresses of
every cons of its argument in some datastructure and checking whether
the next cons is already in there. This implementation needs memory
proportional to the list length. There's a neat O(1) memory
implementation where you have two running pointers through the list,
one advancing by 1 step and the other advancing by 2 steps. In a
circular list, eventually they will meet. In a proper list they will
get to the end.

-- 
Jane - Daria? Come on, the neighbors are starting to talk.
Daria - Um... good. Soon they'll progress to cave drawings and civilization 
will be on its way.