[r6rs-discuss] [Formal] Requirement to detect circular lists

[Abdulaziz Ghuloum]

On Oct 2, 2006, at 7:21 AM, Dan Muresan wrote:

> For a non-circular list, the hare will perform an extra traversal, and 
> the
> tortoise a half-traversal. Thus (lenght) will take 150% more to 
> complete.

No.  Let the hare keep the count, not the tortoise.  I suggest you 
implement
the algorithm first before discussing its performance characteristics.

> OK, I support your comment. Circularity checks make common list 
> operations
> 150% slower for catching a hypothetical bug that no one has seen 
> happen.
> It's a pretty bad trade-off.

Just because you immediately figured out how to implement something
inefficiently does not preclude efficient implementations.

Plus, you don't need a hare and tortoise to perform cycle detection for
length.

Aziz,,,