-----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----- _______________________________________________ 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
