Arc Forumnew | comments | leaders | submitlogin
1 point by akkartik 1190 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))


2 points by rocketnia 1187 days ago | link

"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...?

-----

1 point by akkartik 1187 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 1187 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 1187 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 1187 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.)

-----

1 point by rocketnia 1187 days ago | link

"the rabbit and the hare"

Whoops. I didn't mean that. XD

-----