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

From: Abdulaziz Ghuloum <aghuloum>
Date: Mon Oct 2 07:34:30 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
> 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,,,
Received on Mon Oct 02 2006 - 07:34:31 UTC