[Caml-list] Is it possible to implement this?

[Caml-list] Is it possible to implement this?

[Lukasz Lew]

Let's suppose wy have module with such interface

module X =
 type t (*big data structure*)

 add : string -> t
 delete : t -> ()

And in the other module i keep X.t list, and i want to keep with each of 
them additional data of unknown type [at time of X compilation]

One solution is to have a hash from t to additional data in 
external module, but this would be slow, because of size of t.

Other is to keep with every t int identifier as small as possible, to keep
additional data in array, but this solution isn't very good.

Any ideas?
Lukasz Lew

-------------------
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] Is it possible to implement this?

[Jean-Christophe Filliatre]

Lukasz Lew writes:
 > 
 > Let's suppose wy have module with such interface
 > 
 > module X =
 >  type t (*big data structure*)
 > 
 >  add : string -> t
 >  delete : t -> ()
 > 
 > And in the other module i keep X.t list, and i want to keep with each of 
 > them additional data of unknown type [at time of X compilation]

You could  have a polymorphic  type "'a X.t"  where 'a stands  for the
type of the  associated data, and provide functions  "add_info : 'a ->
'a t -> unit" and "get_info : 'a t -> 'a" in module X.

 > Other is to keep with every t int identifier as small as possible, to keep
 > additional data in array, but this solution isn't very good.

Following this  kind of  idea, you could  do hash-consing of  your X.t
values, so that  they are allocated only once; doing  this, it is easy
to associate a  unique integer to each value in  X.t, which will allow
you to build an efficient map over X.t.

I already wrote an hash-consing module, available here:
http://www.lri.fr/~filliatr/software.en.html

(By  the way,  doing hash-consing  has many  other advantages  such as
saving space, providing O(1) equality, ...)

Hope this helps,
-- 
Jean-Christophe Filliâtre

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