[r6rs-discuss] [Formal] Requirement to detect circular lists
dan-r6rs at omnigia.com
Mon Oct 2 07:21:49 EDT 2006
>> difference. Certainly nothing becomes O(n) instead of O(1). For
>> (length), example, there's just an extra check at each step -- no need
>> for hare-and-tortoise.
> Could you elaborate on this last sentence (I don't see it)?
You're right, it does need hare-and-tortoise. My bad.
Hare-and-tortoise is still O(n), but let's see what the factor is.
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.
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. People working with circular lists know what
they're doing and can implement hare-and-tortoise themselves.
More information about the r6rs-discuss