How to make a value uncomparable

How to make a value uncomparable

[Berke Durak]

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 :
   sig
     type 'a t
     val make : 'a -> 'a t
     val get : 'a t -> 'a
   end
   =
   struct
     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
   end

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

-- 
Berke DURAK

Re: [Caml-list] How to make a value uncomparable

[Christophe Raffalli]

[-- Attachment #1: Type: text/plain, Size: 750 bytes --]


>=20
> module Uncomparable :
>   sig
>     type 'a t
>     val make : 'a -> 'a t
>     val get : 'a t -> 'a
>   end
>   =3D
>   struct
>     type 'a t =3D unit -> 'a
>=20
>     let make x =3D fun _ -> x
>=20
>     let get x =3D x ()
>   end
>=20


--=20
Christophe Raffalli
Universite de Savoie
Batiment Le Chablais, bureau 21
73376 Le Bourget-du-Lac Cedex

tel: (33) 4 79 75 81 03
fax: (33) 4 79 75 87 42
mail: Christophe.Raffalli@univ-savoie.fr
www: http://www.lama.univ-savoie.fr/~RAFFALLI
---------------------------------------------
IMPORTANT: this mail is signed using PGP/MIME
At least Enigmail/Mozilla, mutt or evolution
can check this signature. The public key is
stored on www.keyserver.net
---------------------------------------------


[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 252 bytes --]

Re: [Caml-list] How to make a value uncomparable

[Berke Durak]

Christophe Raffalli wrote:
>> =20
>> module Uncomparable :
>>   sig
>>     type 'a t
>>     val make : 'a -> 'a t
>>     val get : 'a t -> 'a
>>   end
>>   =3D
>>   struct
>>     type 'a t =3D unit -> 'a
>> =20
>>     let make x =3D fun _ -> x
>> =20
>>     let get x =3D x ()
>>   end
>> =20

Indeed, that's a much simpler solution! :)

But there's one minor difference: physical equality works on Weak.t but not on
functions.  But that can be handled by using a ref to a function.

module Structurally_uncomparable :
   sig
     type 'a t
     val make : 'a -> 'a t
     val get : 'a t -> 'a
   end
   =
   struct
     type 'a t = (unit -> 'a) ref
     let make x = ref (fun _ -> x)
     let get x = (!x)()
   end

-- 
Berke DURAK

Re: [Caml-list] How to make a value uncomparable

[Christophe Raffalli]

[-- Attachment #1: Type: text/plain, Size: 794 bytes --]


> 
> But there's one minor difference: physical equality works on Weak.t but
> not on
> functions. 

What do you mean:

# let i x = x;;
val i : 'a -> 'a = <fun>
# i == i;;
- : bool = true
# let j x = x;;
val j : 'a -> 'a = <fun>
# i == j;;
- : bool = false


-- 
Christophe Raffalli
Universite de Savoie
Batiment Le Chablais, bureau 21
73376 Le Bourget-du-Lac Cedex

tel: (33) 4 79 75 81 03
fax: (33) 4 79 75 87 42
mail: Christophe.Raffalli@univ-savoie.fr
www: http://www.lama.univ-savoie.fr/~RAFFALLI
---------------------------------------------
IMPORTANT: this mail is signed using PGP/MIME
At least Enigmail/Mozilla, mutt or evolution
can check this signature. The public key is
stored on www.keyserver.net
---------------------------------------------


[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 252 bytes --]

Re: [Caml-list] How to make a value uncomparable

[Berke Durak]

[-- Attachment #1: Type: text/plain, Size: 231 bytes --]

2008/4/23 Christophe Raffalli <christophe.raffalli@univ-savoie.fr>:

>
> >
> > But there's one minor difference: physical equality works on Weak.t but
> > not on
> > functions.
>
> What do you mean:


I don't know

-- 
Berke Durak

[-- Attachment #2: Type: text/html, Size: 569 bytes --]

Re: [Caml-list] How to make a value uncomparable

[Jon Harrop]

On Wednesday 23 April 2008 18:43:18 Berke Durak wrote:
> 2008/4/23 Christophe Raffalli <christophe.raffalli@univ-savoie.fr>:
> > > But there's one minor difference: physical equality works on Weak.t but
> > > not on
> > > functions.
> >
> > What do you mean:
>
> I don't know

I don't think even uniqueness types can help you there but this tale might at 
least take your mind off it:

A shepherd was looking after his sheep on the side of a deserted road
Suddenly a brand new Porsche screeches to a halt. The driver, a young
man dressed in an Armani suit, Ray Bans, Tag Heuer watch, White Cerutti
shoes, tailor-made mauve shirt, with a Boss tie gets out and says to the
shepherd
'If I can guess how many sheep you have, can I keep one?'
The shepherd looks at the large flock of sheep and says 'Okay'.
The young man connects his laptop to his mobile phone/fax, enters the
NASA website, scans the field using his GPS, opens the database linked
to 60 Excel tables, filled with logarithms and pivot tables, then prints
out a 150 page report on his high tech mini printer.
He studies the reports and says to the shepherd 'You have 1586 sheep'.
The shepherd replies, "That's correct. You can have the pick of my
flock."
The young man packs away his equipment, looks at the flock and puts an
animal into the boot of the Porsche.
As he is about to leave, the Shepherd says,
"If I can guess what your profession is will you return the animal to
me?'
The young man thinks for a minute and says 'Okay'.
The shepherd says 'You are a Management Consultant'.
The young man says' Correct, how did you know?'
The Shepherd replied, 'Simple.
First you came here without being invited.
Second you charged me a fee for something I already knew.
Third, you don't understand anything about my business.'
Now, please can I have my dog back?'

-- 
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
http://www.ffconsultancy.com/products/?e