John Boyle scripsit:
Informally, we can say that your first two expressions can both be
> ... 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?.
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".
That's a non-conformant implementation of R7RS `write`, which is required
> ... 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).
to use labels only in the presence of cycles, not in the presence of
Fortunately, `equal?` is not in any way encoded into Scheme, other than
> ...I still think "equal?, but degrades to isomorphic?" is the most useful
> function for my purposes, but eh, whatever.
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.
That's just a way of encoding the paradoxical fact that one plus infinity
> 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).
is still equal to infinity. If you don't like that, avoid infinite
structures or define your own equality.
Indeed, Chez, Vicare, Ypsilon, Mosh, and IronScheme all implement it
> Meanwhile, Will Clinger has a reference implementation of "unfolding",
> Racket and probably others have full implementations, and R6RS
> specifies it.
correctly. For whatever reason, Larceny returns #f at the REPL.
Ack. I think your definitions are more confusing than the R6RS version.
> By the way, if the "(possibly infinite) unfoldings" definition is
> considered confusing, I'll throw out some suggestions for a precise
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