[Caml-list] Feature proposal: improved compare

[Tom]

I believe the compare function from standard library should be extended to
allow total ordering of functional types (= closures). I suggest something
like...

let old_compare = compare;;

let rec compare a b =
let ar = Obj.repr a in
let br = Obj.repr b in
if Obj.tag ar = Obj.closure_tag && Obj.tag br = Obj.closure_tag then
(* Field 0 of a closure is a pointer of the function code.
Continue if pointers match *)
let d = (-) (Obj.obj (Obj.field ar 0)) (Obj.obj (Obj.field br 0))
in
if d <> 0 then d else
(* now match every other field of the closures - these are the
arguments to partially applied functions *)
let rec f x = if x = Obj.size ar then 0 else
let d = (-) (Obj.obj (Obj.field ar x)) (Obj.obj (Obj.field br
x)) in
if d <> 0 then d else f (x+1)
in
f 0
(* if the two values are not closures, call the old compare. This in
fact is incorrect behaviour, as old compare will fail if it meets
(different) closure values. All the match cases in old compare should be
included in the new compare if the behaviour is to be correct. *)
else old_compare a b;;

This way, one could use for example association lists in order to store
functional values and use List.assoc with them. The improvement over the old
compare is this:

# old_compare (f 0) (f 0);;
Exception: Invalid_argument "equal: functional value".

# compare (f 0) (f 0);;
- : int = 0

- Tom

[Jon Harrop]

On Monday 02 October 2006 21:36, Tom wrote:
> I believe the compare function from standard library should be extended to
> allow total ordering of functional types (= closures). I suggest something
> like...

I believe that won't work with OCaml's GC because it contains a copying
collector, obviating a total ordering over pairs of pointers.

--
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
Objective CAML for Scientists
http://www.ffconsultancy.com/products/ocaml_for_scientists

_______________________________________________
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

[Tom]

>
>
>
> I believe that won't work with OCaml's GC because it contains a copying
> collector, obviating a total ordering over pairs of pointers.

The pointer used in total ordering is points outside the heap, into the
OCaml code (either machine code or byte-code), which, as far as I know, is
neither moved nor collected (although this would actually be a useful
feature, unloading modules...)

[Tom]

With labelled arguments, it doesn't work... unfortunately :D Only, if the
first x arguments are provided (first meaning first in definition of the
function).