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.