Re: [Scheme-reports] Cycle detection problems: #442, #338, "equal?"
Ray Dillinger 30 Aug 2012 19:30 UTC
-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1
On 08/30/2012 11:57 AM, Ray Dillinger wrote:
> The behavior I would prefer, however, is that outlined by Per
> Bothner.
>
> To state it precisely in terms clear enough for the standard and
> also calculated to tell people exactly how to implement it:
>
> "If one operand has a cycle and the other does not, then the
> predicate returns #f. If all have cycles, then iff the printed
> representations of the structures are identical up to the point
> when all have entered their cycles at least twice, then the
> predicate returns #t."
Actually, as I consider the above, there is one case where I'm
not comfortable with this definition. Vectors can have elements
whose printed representation is not part of the "infinite
printed representation" if there is a cycle that starts before
those elements. Consider two arrays, each of which has itself
as its own second element:
V1 ==> #1=#(1 #1 6)
V2 ==> #2=#(1 #2 9)
(equal? V1 v2) ==> ?
The infinite printed representation is identical, well past the
point where both have entered their cycle at least twice. Both
would show "#(1 #(1 #(1 #(1 #(1 #(1 ......" But they can't be
considered equal? because
(equal? (vector-ref V1 2) (vector-ref V2 2)) => #f
It requires cycle-aware print to distinguish the written
representation.
So, given the above, I think it's necessary that equal? should
detect structural isomorphism (written representation under
cycle-aware printing is equal) rather than generation of
identical infinite sequences ("infinite" written representation
up to second entry of cycle is equal).
Bear
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.12 (GNU/Linux)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/
iQEcBAEBAgAGBQJQP79pAAoJEAOzWkqOibfNvzIH/jZBCxouUxtXCDHPvzGMzYwP
dLj+1cNmUGLLLmCyuFyCYtR9y3H52zfKRoWUI9FXEpkgFsVSd5trWmpvs9Q+1het
yY7NfnVYRCftFxRHoCBNKxax/L4X24AWrFlaLfLuy8T93VgJbMgG5R9fnUokeeqZ
bhh8Yy22mjOHuAWitqsG7DqwsbYUeybReh4X29bQyEZce+z65US4MyHpTHMGGA4D
v6jkHgum2BXNqebHPjTBvJ3YY0EtzKv3/Cu8R5BNHPJlly6yCiUYyyydcfZfVkgZ
KfKLCL/b4fe0uCtcBWio8vCl/7q4OkqM/O+bifx1qhwl6AUanVOhyVSIfHS9/9Y=
=dhoB
-----END PGP SIGNATURE-----
_______________________________________________
Scheme-reports mailing list
Scheme-reports@scheme-reports.org
http://lists.scheme-reports.org/cgi-bin/mailman/listinfo/scheme-reports