1 point by akkartik 1754 days ago | link | parent Yes, the print example was just an illustration. It was also a good test for wart; I caught several bugs :) https://github.com/akkartik/wart/compare/686828edba...0e2388.... The tests are pretty self-contained.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))``````
 1 point by akkartik 1751 days ago | link 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 `````` But:`````` x <- '(1 2 3) lastcdr.x <- cdr.x # 1 2 3 2 3 2 3 ... print x 1 2 ...``````-----
 2 points by rocketnia 1750 days ago | link `````` You posted: x <- '(1 2 3) lastcdr.x <- cdr.x # 1 2 3 2 3 2 3 ... print x 1 2 ... `````` Is that the behavior you expect? I would expect "1 2 3 ...", but it looks like the rabbit and the hare meet at the (3 ...) cons and stop.`````` 1 2 3 2 3 2 3 * Print "1". * * Print "2". * * Print "...".``````-----
 1 point by akkartik 1750 days ago | link Yeah I tried it out before posting. I had to take pains in iso to make sure we do one full traversal. With print I didn't care as much.Update: Ack, I found a bug in iso (http://arclanguage.org/item?id=17365):`````` x <- '(1 2 3) y <- '(1 2 4) (do1 nil (<- lastcdr.x x lastcdr.y y)) # Avoid printing the cycles (iso x y) # not nil!``````-----
 2 points by rocketnia 1750 days ago | link 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.)-----