Email list hosting service & mailing list manager


Re: LIST-LENGTH & circular lists Noah Friedman 23 Apr 2001 22:58 UTC

>   But this is scheme, which isn't "pure".  It's not clear to me why the
>   distinction between a pure list & a "side-effectable" list should be
>   made.
>
>People frequently like to work in a "pure" subset of Scheme. Simpler world,
>more axioms about your code & data hold. Sometimes, you work in this world
>in one chunk of your program, then take an impure view for some other piece
>where it's necessary to do so.

Depends on the kinds of problems you're trying to solve.  A circular list
might just be an infinite stream, or it might model some real-world graph
(such as a webmap or cross-referenced directory taxonomy).  I wouldn't
claim the function I posted is useful enough to include in a
general-purpose library.  In fact I'd never seen that algorithm before (a
friend of mine and I worked on it after noticing that the classic
tortoise-hare algorithm detected circular lists but revealed nothing more
about them), so it can't be a problem that people encounter every day.  But
since a couple of people made remarks on this list to effect that this
looked like an "expensive" problem, I just wanted to point out that it's
not especially so.