Re: [Scheme-reports] Cycle detection problems: #442, #338, "equal?"

[John Cowan <cowan@x>]

John Boyle scripsit:

> ... I must say, I assumed that equal? did in fact mean
> "isomorphic/one-to-one mapping", not "(possibly infinite) unfoldings".  I
> was astonished to hear that it was the latter, and that #0=(x . #0#) was
> equal? to #0=(x x . #0#), but Racket confirms it.  At first, I couldn't
> imagine why it would be this way, but now I realize: the list ((x) (x)) is
> not isomorphic to the list (#0=(x) #0#), yet they are considered equal?.

Informally, we can say that your first two expressions can both be
characterized as "a list with an infinite number of x's" and are thus
equal; the last two expressions are similarly "a list of two elements,
each of which is a list containing x".

> ... I am tempted to suggest, as you seem to do, that we take a hybrid
> approach and have "equal?" degrade to "isomorphic?" when a cycle is
> detected (the way "write" is probably going to degrade to "write-shared"
> when a cycle is detected).

That's a non-conformant implementation of R7RS `write`, which is required
to use labels only in the presence of cycles, not in the presence of
structure-sharing.

> ...I still think "equal?, but degrades to isomorphic?" is the most useful
> function for my purposes, but eh, whatever.  

Fortunately, `equal?` is not in any way encoded into Scheme, other than
its use in defining `assoc` and `member` (and these now allow you to
provide your own equality predicate).  It's a straightforward matter to
roll a predicate that does exactly what your particular application needs.

> Actually, come to think of it, there is one fact about equal? that is true
> for all non-cyclic structures that isn't true under unfolding: if (equal? a
> b), then not (equal? (cons <something> a) b).  

That's just a way of encoding the paradoxical fact that one plus infinity
is still equal to infinity.  If you don't like that, avoid infinite
structures or define your own equality.

> Meanwhile, Will Clinger has a reference implementation of "unfolding",
> Racket and probably others have full implementations, and R6RS
> specifies it.

Indeed, Chez, Vicare, Ypsilon, Mosh, and IronScheme all implement it
correctly.  For whatever reason, Larceny returns #f at the REPL.

> By the way, if the "(possibly infinite) unfoldings" definition is
> considered confusing, I'll throw out some suggestions for a precise
> definition:

Ack.  I think your definitions are more confusing than the R6RS version.
What I really don't understand is what "regular trees" means in the
phrase "(possibly infinite) unfoldings are equal as regular trees."
I know what regular tree grammars are, but what are regular trees?


-- 
Clear?  Huh!  Why a four-year-old child         John Cowan
could understand this report.  Run out          cowan@x
and find me a four-year-old child.  I           http://www.ccil.org/~cowan
can't make head or tail out of it.
        --Rufus T. Firefly on government reports

_______________________________________________
Scheme-reports mailing list
Scheme-reports@x
http://lists.scheme-reports.org/cgi-bin/mailman/listinfo/scheme-reports