I'd assumed I could apply Floyd's hare to handle cars as well, but you're right, now I'm not so sure. The key difficulty is that there's two dimensions, so does the number of hares double each iteration?

Here's a flat-cycle-detecting iso I've been playing with:

def (iso a b)
((afn ((a harea|through) (b hareb|through))
(if ~list?.a
(a = b)
(addr.a = addr.harea)
(addr.b = addr.hareb)
:else
(and (iso car.a car.b) # Can't detect cycles through car.
(self `(,cdr.a :through ,cdr+cdr.harea)
`(,cdr.b :through ,cdr+cdr.hareb)))))
(list a :through cdr.a)
(list b :through cdr.b))

"The key difficulty is that there's two dimensions, so does the number of hares double each iteration?"

Hmm. As the tortoise goes down branches, its location becomes indeterminate. As the hare goes down branches, its location becomes indeterminate relative to the tortoise, so we might need multiple hare markers per branch if we're doing a tortoise-directed search. If we try using the hare to direct the search instead, then we may still need to keep a growing history of hare locations on each branch so the tortoise can follow.

Either way, keeping a hash table sounds more straightforward to me.

Are you using this algorithm properly? I haven't seen any of your example code do a second pass to find out where the cycle begins and what its period is. But maybe you don't need to...?

I'm just taking a constant-factor hit :) A few extra iterations doesn't change the result for either print or iso. And for cycles that loop back all the way to the start it turns out there's zero overhead.

x <- '(1 2 3)
lastcdr.x <- x # 1 2 3 1 2 3 1 ...
print x
1
2
3
... # exactly one iteration

Here's a slightly different bug I found before your update. It's another case where I don't know what behavior you expect, but it probably isn't this. :-p

(do (a <- '(1 2 3)) (lastcdr.a <- cdr.a) nil)
=> nil
(do (b <- '(1 2 3 2 3)) (lastcdr.b <- cdr.b) nil)
=> nil
(not+not+iso a b)
=> nil
(not+not+iso b a)
=> 1

(I'm using not+not+iso so it returns a predictable value rather than an address.)