[r6rs-discuss] [Formal] Requirement to detect circular lists
aghuloum at cs.indiana.edu
Mon Oct 2 07:34:31 EDT 2006
On Oct 2, 2006, at 7:21 AM, Dan Muresan wrote:
> For a non-circular list, the hare will perform an extra traversal, and
> tortoise a half-traversal. Thus (lenght) will take 150% more to
No. Let the hare keep the count, not the tortoise. I suggest you
the algorithm first before discussing its performance characteristics.
> OK, I support your comment. Circularity checks make common list
> 150% slower for catching a hypothetical bug that no one has seen
> 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
More information about the r6rs-discuss