on polymorphic compare and objects

[Peng Zang <peng.zang@gmail.com>]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

I recently came across a post on Janest lamenting the perils of polymorphic 
compare.

  http://ocaml.janestcapital.com/?q=comment/reply/33

They make a great point, and I thought of a solution that has worked well for 
me in the past few months that I would like to share, in part, to solicit 
feedback from the community.

Here is my approach.  It is, in part, excerpted from a conversation with Brain 
Hurt and also posted on the Janest blog.  As warning, my approach does use 
some magic and OCaml guts but no more than what is made available for OCaml/C 
interface.  It is also mostly hidden once done.

- ----

The (compare) function has the signature ('a -> 'a -> bool).  That means it is 
a function that imposes a total ordering for *all* types -- even those that 
have not yet been defined. Clearly, it cannot be the desired ordering for all 
(and future) types.  If OCaml had a "content" equality function (ie. two 
things are equal if they can be used
interchangably in pure functions) it would have a similar problem.

It is my opinion that this approach is really just for convenience and
performance reasons.  The right solution would use something like
type classes or go with Java's object based solution (eg. Comparable
interface).

Here's my solution to this.  I modify the (compare) and other similar 
functions to check for objects and use its appropriate method if available.  
In otherwords, if you call compare on a (int,int) tuple, it has OCaml's 
standard behavior.  But if you call compare on a [int,int] tuple class, it 
will use the class' compare method.  This hybrids
between OCaml's polymorphic solution and the Java, method-dispatch solution.

One might also think of it as a hook.  If the user defines some type that has
unique comparison behavior he/she can do so by wrapping the type in a class
and specifying the unique behavior via the compare method.  This means the
rest of the code never needs to know and use special compare functions.  It
can always use compare, knowing that it will automatically do the right
thing.

In this way (compare) and (content-equals) can actually be well defined for
all (including future) types.  Let's take as an example, the content-equals
function which I'll just call equal for now.  (equal) has a very specific
semantic meaning: it returns true if its two arguments are exchangable in a
pure context (ie. no side-effects).  (equal) is well defined for all simple
types: int, float, string, etc..  For objects, we require that all objects
implement an equal method that satisfies the semantic contract.  Thus (equal)
the function is also well defined on objects.  For all other types, whatever
they may be, either the default structural comparison behavior of (equal)
satisfies the semantic contract or it does not.  If it does, then (equal) is
well defined.  If it does not, we require it to be wrapped in an object so
that an appropriate behavior can be specified.

As a concrete example consider:

  type xycoord = (int, int)

As it happens, structural equality is what we want.  Since (equal) already
does this we are done.

Now consider:

  type rational_number = (int, int)

Here, structural equality is not what we want.  (1/2) is the same rational
number as (2/4) but they are not structurally equal.  Thus in order to satisfy
the semantic contract of (equal) we must instead do:

  class type rational_number = object
    method equal : rational_number -> bool
    ...
  end


Meanwhile, a function like List.assoc, but defined using (equal), works
equally well on both types.

This approach lets you keep the OCaml approach of a polymorphic compare/equal
function, but does not limit you to a single algorithm for performing the 
comparison.  It buys you the power of objects (much like that of type 
classes) but without the requirement that everything be an object.  I have 
found it to be a sweet spot and use it in my code regularly.

- ----


As always, I welcome any comments, suggestions, questions or flames =]


Peng
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v2.0.7 (GNU/Linux)

iD8DBQFIvcevfIRcEFL/JewRAqQaAJ485qiwtMKy5W9dJbIvNzklH/DZ3wCfQlR6
UrtMhcho4xm4mII2Depv+vs=
=HZ9F
-----END PGP SIGNATURE-----