[Caml-list] getting the type of a polymorphic data ?

[Caml-list] getting the type of a polymorphic data ?

[Diego Olivier Fernandez Pons]

    Bonjour,

In a branch and bound program I give the user a generic polymorphic
data structure to represent decision variables, namely a set of
intervals - (domains decrease monotonically)

x = [0 .. 1] U [2 .. 3[
y = [3,5  14,8]

As usual in branch and bound, a value is tried (x = 1) and removed of
the domain if the corresponding branch raises a 'No solution'
exception (x = [0 .. 1[ U [2 .. 3[)

In a preprocessing phase I would like to change the representation of
the decision variables according to their type to avoid degenerancies
like

[0 .. 1[ U ]2 .. 3[ U ]4 .. 5[ -> [0] in the integer case but not with
floats

The problem is that I don't know how to catch the type of a
polymorphic data structure (is this even possible with some magic ?)
to be able to write something like

let x' = match (somemagic.type_of x) with
           | INT -> IntSet.from_poly x
           | FLOAT -> FloatIntervalSet.from_poly x
           | _ -> x

Any hints ?


         Diego Olivier

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] getting the type of a polymorphic data ?

[Diego Olivier Fernandez Pons]

    Bonjour,

> The problem is that I don't know how to catch the type of a
> polymorphic data structure (is this even possible with some magic ?)
> to be able to write something like
>
> let x' = match (somemagic.type_of x) with
>           | INT -> IntSet.from_poly x
>           | FLOAT -> FloatIntervalSet.from_poly x
>           | _ -> x

I have just realized I really do not need the 'type' of the
polymorphic data, just to know if it is isomorphic to integers (to be
able to properly use Hashtbl.hash)

It seems that Obj.is_int does exactly that (determining if a type is
isomorphic to a subset of integers).

        Objective Caml version 3.08.0

# Obj.is_int (Obj.repr 'a');;
- : bool = true
# type x = A | B;;
type x = A | B
# Obj.is_int (Obj.repr A);;
- : bool = true
# Obj.is_int (Obj.repr 1);;
- : bool = true
# Obj.is_int (Obj.repr "a");;
- : bool = false
# type x = A of int * int | B of int;;
type x = A of int * int | B of int
# Obj.is_int (Obj.repr (A (1, 0)));;
- : bool = false

Is it reasonable to admit that if Obj.is_int is true for x and y then
Hashtbl.hash is injective ?

hash x = hash y => x = y (for structural polymorphic equality)

In other terms does 'Obj.is_int x' implies that x is 'perfectly
hashable' ?


        Diego Olivier

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] getting the type of a polymorphic data ?

[Damien Doligez]

On Aug 12, 2004, at 14:09, Diego Olivier Fernandez Pons wrote:

> It seems that Obj.is_int does exactly that (determining if a type is
> isomorphic to a subset of integers).

No, not exactly:

         Objective Caml version 3.09+dev0 (2004-07-13)

# type x = A | B of int;;
type x = A | B of int
# Obj.is_int (Obj.repr A);;
- : bool = true
# Obj.is_int (Obj.repr (B 1));;
- : bool = false

All Obj.is_int tells you about the _type_ of its argument is that,
if it returns true then at least one of the type's values is
represented as an integer.


> Is it reasonable to admit that if Obj.is_int is true for x and y then
> Hashtbl.hash is injective ?
>
> hash x = hash y => x = y (for structural polymorphic equality)

Not quite.

# Hashtbl.hash 0x4000_0000;;
- : int = 0
# Hashtbl.hash 0;;
- : int = 0

-- Damien

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] getting the type of a polymorphic data ?

[Diego Olivier Fernandez Pons]

    Bonjour,

> Not quite.
>
> # Hashtbl.hash 0x4000_0000;;
> - : int = 0
> # Hashtbl.hash 0;;
> - : int = 0

Yes but

# let x = 0x4000_0000;;
val x : int = -1073741824

If the only case of collision is due to modulo 2^31 then it is - at
least for me - reasonable since the user is supposed to have a minimal
knowledge of computer science. And Caml allows him to check with
max_int / min_int for overflows.

(* obviously doesn't typecheck, just for example *)

let hashable = function x ->
  x < max_int && x > min_int && Obj.is_int (Obj.repr x)

hashable x, y => hash injective




        Diego Olivier

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] getting the type of a polymorphic data ?

[Marcin 'Qrczak' Kowalczyk]

W liście z czw, 12-08-2004, godz. 15:57 +0200, Diego Olivier Fernandez
Pons napisał:

> If the only case of collision is due to modulo 2^31 then it is - at
> least for me - reasonable since the user is supposed to have a minimal
> knowledge of computer science. And Caml allows him to check with
> max_int / min_int for overflows.

I'm not sure what do you mean, but there are 2^31 int values, half of
them negative, which map to 2^30 hashes, all non-negative. Hashing an
int stripts its sign bit.

This was on 32-bit architectures. On 64-bit architectures hashes are
still modulo 2^30, but there are 2^63 different ints.

-- 
   __("<         Marcin Kowalczyk
   \__/       qrczak@knm.org.pl
    ^^     http://qrnik.knm.org.pl/~qrczak/

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] getting the type of a polymorphic data ?

[Diego Olivier Fernandez Pons]

    Bonjour,

> I'm not sure what do you mean, but there are 2^31 int values, half
> of them negative, which map to 2^30 hashes, all non-negative.
> Hashing an int stripts its sign bit.

Bon... J'avais raté celle là. On peut raisonnablement se contenter
d'entiers positifs pour les variables de décision mais si d'une part
hash ne laisse pas invariant le type entier, d'autre part on ne peut
pas faire la différence entre un véritable entier et une valeur
isomorphe c'est perdu d'avance.


        Diego Olivier



-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] getting the type of a polymorphic data ?

[Diego Olivier Fernandez Pons]

    Bonjour

[Je poste la réponse à une question qui m'a été posée en dehors de la
liste car mes explications semblent ne pas avoir été claires]

> mal compris ton problème -- pourquoi ne pas définir un type du genre :
>
> type number = Int of int | Float of float
>
> et faire un matching qui ressemblerait à
>
> let x' = match x with
>          | Int x -> IntSet.from_poly x
>          | Float x -> FloatIntervalSet.from_poly x


Parce que ce n'est pas moi qui définit x. En fait (voir message
initial) x est un ensemble de type polymorphe car l'utilisateur est
supposé pouvoir y mettre ses propres types.

Voici la situation que je veux _éviter_ (exemple tiré de FaCiLe -
Pascal Brisset et Nicolas Barnier)

let
  yellow = 0 and
  blue = 1 and
  green = 2
in
  let x = IntDomain.from_list [0; 1; 2]

A la place je veux

type color = Yellow | Blue | Green

let x = Domain.from_list [Yellow ; Blue; Green]

Mais il faut que la partie interne de la librairie, elle, manipule un
ensemble d'entiers (pour des questions de performance puisqu'il s'agit
d'optimisation combinatoire).

D'où l'idée simple

let x = Domain.from_list [(hash Yellow) ; (hash Blue) ; (hash Green)]

ou encore

let x = Domain.from_list_hashed [ Yellow ; Blue ; Green]


Mais pour que cette optimisation soit correcte, il faut que hash x =
hash y => x = y, d'où ma question.

Autre précision, ce n'est pas grave si un type est isomorphe à un
entier mais le compilateur ne le voit pas par exemple

type x = A of int

Obj.is_int (A 1)
# false


        Diego Olivier

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] getting the type of a polymorphic data ?

[Jean-Baptiste Rouquier]

> Is it reasonable to admit that if Obj.is_int is true for x and y then
Hashtbl.hash is injective ?
No.

# type foo = A | B;;
# let _ = Obj.is_int (Obj.repr 0);;
- : bool = true
# let _ = Obj.is_int (Obj.repr A);;
- : bool = true
# let _ = Hashtbl.hash A;;
- : int = 0
# let _ = Hashtbl.hash 0;;
- : int = 0

The purpose of Hashtbl.hash is exactly no to be injective ! And hashing lists
can't be injective.

        Objective Caml version 3.07+2
# let _ = Hashtbl.hash [0;1];;
- : int = 65599
# let _ = Hashtbl.hash [65599;0];;
- : int = 65599

What you are looking for is a function that associates a unique int to a
variable of any type. This is Oo.id.
As you said, hash is neither injective on int, nor does it allow to distinguish
between types isomorphs to (a subset of) int.

But let's try to first state the requirement :
- the user define it's own types, foo and bar. We can ask him to provide some
functions to handle these types.
- you want a way to print the result x (of type foo or bar) of a computation
with a user provided help message. This help message doesn't depend on the value
of x.
- you want to manipulate the types foo and bar either as int or floats (not both
for the same type), for efficiency.

My approach is to first transform the user defined type into your own good
representation, using user provided functions, then work on int and float for
the branch and bound, without type tricks, and work on more sophisticated types
for printing.
The user has to say whether his type is isomorph to int (and provide the
conversions functions) or to float (ditto). It's safer than trying to guess it
with the Obj module.
You could provide defaults for those conversions functions, based on Obj / hash
tricks, with lots of warnings.

type 'a range =
  | Single of 'a
  | Interval of 'a * 'a

type domain =
  | Discrete of int range list
  | Continuous of float range list (* is Single meaningful ? *)

Your function
[0 .. 1[ U ]2 .. 3[ U ]4 .. 5[ -> [0]
can now be written
val simplify : domain -> domain



Now printing the results. The property lists is a general solution which is good
for your problem. You can also have a specialized (trivial) mechanism, see
below. The core idea is that you must have two different types :
 - one for doing the computations. For efficiency it's int or float.
 - one for printing the results. This one holds the value (possibly converted
back to user defined type) and the help / description string.

# type 'a result = 'a * string;;
# let new_result (a:'a) description = ((a,description) : 'a result);;
val new_result : 'a -> string -> 'a result = <fun>
# let print_int ((a,d): int result) = Printf.printf "%s is %d\n%!" d a;;
val print_int : int result -> unit = <fun>
# let print_float = ...
# let x = new_result 10 "the number of elements in the knapsack";;
val x : int result = ...
# print_int x;;
the number of elements in the knapsack is 10
- : unit = ()

Jean-Baptiste.

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] getting the type of a polymorphic data ?

[Diego Olivier Fernandez Pons]

    Bonjour,

> > Is it reasonable to admit that if Obj.is_int is true for x and y then
> > Hashtbl.hash is injective ?
>
> No.
>
> # type foo = A | B;;
> # let _ = Obj.is_int (Obj.repr 0);;
> - : bool = true
> # let _ = Obj.is_int (Obj.repr A);;
> - : bool = true
> # let _ = Hashtbl.hash A;;
> - : int = 0
> # let _ = Hashtbl.hash 0;;
> - : int = 0

I meant injective for a given (fixed) type. Obviously it won't in a
completely general case !

> The purpose of Hashtbl.hash is exactly no to be injective ! And
> hashing lists can't be injective.

That is why I said "isomorphic to a (finite) subset of (machine)
integers". And I said "isomorphic", not "in bijection" to be able to
add a few properties behind when needed and exclude the N x N ~ N
argument.

        Diego Olivier

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] getting the type of a polymorphic data ?

[Diego Olivier Fernandez Pons]

    Bonjour,

> # type 'a result = 'a * string;;
> # let new_result (a:'a) description = ((a,description) : 'a result);;
> val new_result : 'a -> string -> 'a result = <fun>
> # let print_int ((a,d): int result) = Printf.printf "%s is %d\n%!" d a;;
> val print_int : int result -> unit = <fun>
> # let print_float = ...
> # let x = new_result 10 "the number of elements in the knapsack";;
> val x : int result = ...
> # print_int x;;
> the number of elements in the knapsack is 10
> - : unit = ()

Here is the problem of this approach

# let complex_computation = fun x y -> x + y
val complex_computation : int -> int -> int = <fun>

let x = simple_computation () and
    y = simple_computation ()

let z = complex_computation x y

Now I what to add a comment to x to print intermediate results and
check the first computation is correct. In your approach, this lifts x
: int on x : int result. But what will then be the type of
complex_computation ?

int result -> int -> int ?
int -> int result -> int ?
int result -> int result -> int ?
int result -> int result -> int result ?


        Diego Olivier

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners