Continuing this conversation about equality...
On Aug 9, 2009, at 9:20 AM, David Allsopp wrote:
Ivan Chollet wrote:
I would have thought physical equality implies structural equality,
but it
doesn't seem like it.
Can you please explain to me what’s wrong there?
"It does" - but only with the given caveat that comparison of cyclic
structures may not terminate. Pervasives.compare has a similar
restriction,
although note that [compare q q] in your example does return 0
(which is
lucky or it would be a bug as the docs for Pervasives.(==) state
that [x ==
y] => [compare x y = 0]).
Let me start with a few pedantic comments about the documentation of
(==):
First, what David says isn't *quite* what the documentation says. The
documentation only says this is [x==y] implies [compare x y = 0] for
non-mutable structures. And in fact, what the documentation says is
surprisingly weak: an implementation could define (==) as *always
false* for non-mutable structures and yet satisfy the documentation.
I'm not sure of the right way to reword it, but this loophole in the
specification seems undesirable.
My other issue is that the description of (==) for mutable structures
doesn't specify that it is symmetric; reading the documentation
literally only implies that e1 is a substructure of e2. Even just
adding 'and vice versa' might clean this up:
e1 == e2 is true if and only if physical modification of e1 also
affects e2 and vice versa
Okay, now for more substantive questions:
The notes in http://caml.inria.fr/mantis/view.php?id=3322 may be of
interest
too...
I hadn't paid attention to the distinction drawn between 'may not
terminate' and 'does not terminate' until I read the discussion at
that link, but it's relevant to my question below...
On Aug 9, 2009, at 9:55 AM, Alain Frisch wrote:
On 8/9/2009 2:06 PM, ivan chollet wrote:
I would have thought physical equality implies structural equality,
but
it doesn’t seem like it.
Can you please explain to me what’s wrong there?
There are two modes for the generic comparison. The total mode
(Pervasives.compare) creates a total ordering between values (except
for functional values and custom blocks with no comparison function)
and uses physical equality as a shortcut to cut the recursive
traversal of sub-values. The non-total mode (used by the operators =
< > <= >=) has a different behavior for NaN values ([nan <= x], [x
<= nan], and [nan = x] all return false, including when x is nan)
and does not use the physical equality shortcut (so that [let x =
(nan, nan) in x = x] returns false).
In terms of 'may not' versus 'does not' terminate, I just noticed that
the current documentation for (=) says 'may not terminate' while the
documentation for (>=) says 'does not terminate'. However, the example
cited in the link above:
type t = { a : t };;
let rec x = { a = x } in x = x
doesn't terminate in OCaml 3.11. This seems to be about as simple a
cyclic structure as there is, so shouldn't (=)'s documentation say
'Equality between cyclic structures does not terminate.'?
Also, the documentation for Pervasives.compare says 'may not
terminate'. Is this supposed to imply that it uses the shortcut Alain
mentions (because if it did not use physical equality as a shortcut
then it would say 'does not terminate')? Or is this shortcutting meant
to be undocumented?
And is there any reason, aside from NaN values, that (=) does *not*
use physical equality as a shortcut? The only other reason I can think
of is that, in cases where things are in fact *not* physically equal,
checking physical equality would introduce a small overhead.
In any case, if I have a data structure which I know does not contain
any NaNs (for example, maybe it doesn't contain any floats
whatsoever), is there ever a reason I should prefer (=) to (compare x
y = 0)? It sounds to me like compare is preferable because of its
shortcutting behavior.
-Elnatan
_______________________________________________
Caml-list mailing list. Subscription management:
http://yquem.inria.fr/cgi-bin/mailman/listinfo/caml-list
Archives: http://caml.inria.fr
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
Bug reports: http://caml.inria.fr/bin/caml-bugs