I am not sure, but I believe this is the algorithm used. Perhaps that will help you understand?
http://www.cs.indiana.edu/~dyb/pubs/equal.pdf Also, check out the tortoise and hare algorithm, described here: https://en.wikipedia.org/wiki/Cycle_detection Robby On Tue, Sep 13, 2016 at 9:25 AM, Dupéron Georges <[email protected]> wrote: > I'm writing a prop:equal+hash for a recursive data structure, and I noticed > that it takes several comparisons of pairs of values which are eq? before > equal? realises that there is a cycle, and stops. > > Below is the code for the trivial case, where the implementation of equality > just calls itself on the same values. > > #lang racket > > (struct s () > #:property prop:equal+hash > (list (λ (a b r) (display ".") (r a b)) > (λ (a r) (display "!") (r a)) > (λ (a r) (display "!") (r a)))) > > (equal? (s) (s)) ;; => prints 26 "." > (equal-hash-code (s)) ;; => prints 128 "!" > (equal-secondary-hash-code (s)) ;; => prints 128 "!" > > Why doesn't it stop immediately after the first cycle? > > Also, where do these magical numbers (26 and 128) come from? I grepped the C > source, but couldn't find anything relevant. The numbers 26 and 128 seem to > be independent of the equality function, so it does not sound like a change > of behaviour once the stack overflows, for example. > > -- > You received this message because you are subscribed to the Google Groups > "Racket Users" group. > To unsubscribe from this group and stop receiving emails from it, send an > email to [email protected]. > For more options, visit https://groups.google.com/d/optout. -- You received this message because you are subscribed to the Google Groups "Racket Users" group. To unsubscribe from this group and stop receiving emails from it, send an email to [email protected]. For more options, visit https://groups.google.com/d/optout.
