English version
Accueil     À propos     Téléchargement     Ressources     Contactez-nous    

Ce site est rarement mis à jour. Pour les informations les plus récentes, rendez-vous sur le nouveau site OCaml à l'adresse ocaml.org.

Browse thread
How to make a value uncomparable
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
Date: 2008-04-23 (13:49)
From: Berke Durak <berke.durak@e...>
Subject: How to make a value uncomparable
Well, as comparing non-canonical datastructures such as Sets and Maps with Pervasives.compare is unsafe,
I was thinking of ways to make sure that you don't do such a thing.

Our resident type experts could tell us if uniqueness types could be used for that purpose, but if you're
willing to settle for run-time safety, here is a little solution.

Pervasives.compare will refuse to run on heap values wrapped in an Abstract_tag, whose purpose is to stop the
GC from nosing below the tag.  So if you have a value that's not Pervasives.compare-comparables, you can wrap
it inside such a tag, and any call to Pervasives.compare will raise an invalid_arg.

But how?  You could of course write a piece of native code, but it happens that the Abstract_tag is used by
the Weak module.  So here's an Uncomparable module, that makes any value run-time Pervasives-uncomparable,
at a cost of six extra words per value (if I'm correct).

module Uncomparable :
     type 'a t
     val make : 'a -> 'a t
     val get : 'a t -> 'a
     type 'a t = 'a * 'a Weak.t

     let make x =
       let w = Weak.create 1 in
       Weak.set w 0 (Some x);
       (x, w)

     let get (x, _) = x

# #use "mkuncmp.ml";;
module Uncomparable :
   sig type 'a t val make : 'a -> 'a t val get : 'a t -> 'a end
# Uncomparable.make 33;;
- : int Uncomparable.t = <abstr>
# let x = Uncomparable.make 33;;
val x : int Uncomparable.t = <abstr>
# let y = Uncomparable.make 33;;
val y : int Uncomparable.t = <abstr>
# compare x y;;
Exception: Invalid_argument "equal: abstract value".
# Uncomparable.get x;;
- : int = 33
# Uncomparable.get y;;
- : int = 33