[racket-dev] Set Equality with Cyclic Structure is not as Expected

From: Daniel King (danking at ccs.neu.edu)
Date: Mon May 7 18:33:02 EDT 2012

Hi,

The following code snippet is a bit confusing to me. Sets with cyclic structure
are not equal? even though they meet my intuitive definition of equal. I'm
curious exactly where my intuition goes wrong.

I imagine the reason why Racket can conclude that the lists are equal is because
the ordering of the list provides a necessary level of disambiguation. With a
set, Racket cannot be certain which element should match between the two
data, and this means potentially following cycles forever? I'm not entirely
clear on my reasoning, but I think this must be related to the root cause.

Note in the following snippet the let* forms differ only in the data constructor
used: `set' in the first form and `list' in the second form.

racket@> (let* ((a-box (box #f))
                (b-box (box #f))
                (a (set 1 a-box))
                (b (set 1 b-box)))
           (set-box! a-box a)
           (set-box! b-box b)
           (displayln a)
           (displayln b)
           (equal? a b))
#0=#<set: 1 #&#0#>
#0=#<set: 1 #&#0#>
#f
racket@>  (let* ((a-box (box #f))
                 (b-box (box #f))
                 (a (list 1 a-box))
                 (b (list 1 b-box)))
            (set-box! a-box a)
            (set-box! b-box b)
            (displayln a)
            (displayln b)
            (equal? a b))
#0=(1 #&#0#)
#0=(1 #&#0#)
#t

P.S.

For future reference, is this more of users@ material or dev@ material?

--
Dan King
College of Computer and Information Science
Northeastern University

Posted on the dev mailing list.