polymorphically comparable Maps?

polymorphically comparable Maps?

[Thorsten Ohl]

Does anybody know of a fast data structure for (applicative)
association tables over ordered types (like Map in the standard
library) with the property that identical maps will have an identical
representation?  Sorted association lists work, but have linear access
and insertion.  Is there something logarithmical (even with an OCaml
implementation)?

Thanks,
-Thorsten

[ If anybody wonders: I want/need polymorphic comparison, because the
  Maps are part of a recursive datastructure. ]
-- 
Thorsten Ohl, Physics Department, TU Darmstadt -- ohl@hep.tu-darmstadt.de
http://heplix.ikp.physik.tu-darmstadt.de/~ohl/ [<=== PGP public key here]

Re: polymorphically comparable Maps?

[Jean-Francois Monin]

> Does anybody know of a fast data structure for (applicative)
> association tables over ordered types (like Map in the standard
> library) with the property that identical maps will have an identical
> representation?  Sorted association lists work, but have linear access
> and insertion.  Is there something logarithmical (even with an OCaml
> implementation)?
> 
> Thanks,
> -Thorsten

I've just finished an in-place polymorphic version of splay trees,
with quite good perf. Splay trees (Tarjan & Sleator) are binary trees
where often accessed data tend to be near the root.

Here is the current mli.  Only iter and fold are still not
implemented, because I am currently experimenting this structure on an
application where they are not used. I can send the whole thing if you
are interested.

-- 
Jean-Francois Monin, CNET DTL/MSV,          Tel +33 2 96 05 26 79
2 av. Pierre Marzin, 22307 Lannion, France  Fax +33 2 96 05 39 45
SANS TRAIT D'UNION :      JeanFrancois.Monin@cnet.francetelecom     

-----------------------------------------------------------
(* splay.mli *)
(* NOT THREAD SAFE : env needs a mutex *)
(* WARNING : compare must not raise anu exception *)

module type OrderedType =
  sig
    type tt
    type tk
    val compare_int : tt -> tt -> int
    val compare_ext : tk -> tt -> int
    val print : tt -> unit
  end

module type S =
  sig
    type eltt
          (* The type of elements in the tree. *)
    type eltk
          (* The type of keys used for searching in the tree. *)
    type t
          (* The type of trees. *)
    exception Already_there
    exception Is_empty
    val print : t -> unit
	(* prints a tree *)
    val create: unit -> t
          (* The empty tree. *)
    val is_empty: t -> bool
        (* Test whether a tree is empty or not. *)
    val find: eltk -> t -> eltt
        (* [find x s] is an element y of [s] such that [compare_ext x y = 0]. *)
    val add: eltt -> t -> unit
        (* [add x s] adds the element [x] to the tree [s],
           If [x] was already in [s], [Already_there] is raised. *)
    val remove: eltk -> t -> unit
        (* [remove x s] returns a tree containing all elements of [s],
           except [y] such that compare_ext x y = 0.
	   If [x] was not in [s], TO BE COMPLETED. *)
(*
    val iter: (eltt -> unit) -> t -> unit
    val fold: (eltt -> 'a -> 'a) -> t -> 'a -> 'a
*)
    val cardinal: t -> int
        (* Return the number of elements of a tree. *)
    val elements: t -> eltt list
        (* Return the list of all elements of the given tree.
           The returned list is sorted in increasing order with respect
           to the ordering [Ord.compare_int], where [Ord] is the argument
           given to [Set.Make]. *)
    val min_elt: t -> eltt
        (* Return the smallest element of the given tree
           (with respect to the [Ord.compare_int] ordering), or raise
           [Not_found] if the tree is empty. *)
    val max_elt: t -> eltt
        (* Same as [min_elt], but returns the largest element of the
           given tree. *)
    val choose: t -> eltt
        (* Return one element of the given tree, or raise [Not_found] if
           the tree is empty. Which element is chosen is unspecified,
           but equal elements will be chosen for equal trees. *)
  end

module Make(Ord: OrderedType):
    (S with type eltt = Ord.tt and type eltk = Ord.tk)
        (* Functor building an implementation of the tree structure
           given a totally ordered type. *)

Re: polymorphically comparable Maps?

[Stefan Monnier]

>>>>> "Thorsten" == Thorsten Ohl <ohl@hep.tu-darmstadt.de> writes:
> library) with the property that identical maps will have an identical
> representation?  Sorted association lists work, but have linear access
> and insertion.  Is there something logarithmical (even with an OCaml
> implementation)?

I can't think of any obvious good answer, but if you can live with explicit
`canonicalization' (linear time) steps in order to then get logarithmical
access and identical representation, then some kind of binary tree can do the
job.
Of course, equality comparison (although simple thanks to the identical
representation) will still be linear, so it doesn't buy you much since
equality comparisons of non-balanced binary trees (or pretty much any map of
ordered types) can also be done fairly simply in linear time.

So why exactly do you want that representation to be `identical' ?


	Stefan

Re: polymorphically comparable Maps?

[Adam P. Jenkins]

Stefan Monnier writes:
 > >>>>> "Thorsten" == Thorsten Ohl <ohl@hep.tu-darmstadt.de> writes:
 > > library) with the property that identical maps will have an identical
 > > representation?  Sorted association lists work, but have linear access
 > > and insertion.  Is there something logarithmical (even with an OCaml
 > > implementation)?
 >
 > I can't think of any obvious good answer, but if you can live with
 > explicit `canonicalization' (linear time) steps in order to then
 > get logarithmical access and identical representation, then some
 > kind of binary tree can do the job.  Of course, equality comparison
 > (although simple thanks to the identical representation) will still
 > be linear, so it doesn't buy you much since equality comparisons of
 > non-balanced binary trees (or pretty much any map of ordered types)
 > can also be done fairly simply in linear time.
 > 
 > So why exactly do you want that representation to be `identical' ?

I almost sent in the same answer you gave, but then realized that I'd
missed the significance of the word "polymorphic" in the subject.  The
polymorphic comparison functions in ocaml -- (<), (<=), compare,
etc. -- cannot be overloaded for user-defined types, so if you want
your Map datatype to be able to work with the polymorphic comparison
functions then you need to make semantically identical maps also be
structurally identical.  

As for why one would want the map datatype to be polymorphically
comparable, if you want a map to be part of some other datastructure,
such as a list of maps, and want to be able to compare two lists of
maps using, say, (=), then the maps need to be structurally identical
for this to work.

Adam

-- 
Adam P. Jenkins 
ajenkins@netway.com

Re: polymorphically comparable Maps?

[Thorsten Ohl]

Stefan Monnier <monnier+lists/caml/news/@tequila.cs.yale.edu> writes:

> I can't think of any obvious good answer, but if you can live with
> explicit `canonicalization' (linear time) steps in order to then get
> logarithmical access and identical representation, then some kind of
> binary tree can do the job.

Insertion is also important.  Before I fell back to sorted lists, I
tried canonicalization at every insertion and it killed performance.

Since I can live with a small probability for failing matches in early
phases (they will only hurt performance, but never correctness), I
might attempt a staged approach with delayed canonicalization.

> So why exactly do you want that representation to be `identical' ?

I represent elements of freely generated abelian groups as maps from
the generators to their multiplicity in the element.  These abelian
groups appear in recursive data structures (e.g. to represent
algebraic expressions).  Therefore the easiest approach uses the
polymorphic comparison function in the maps.

I might eventually replace the polymorphic comparison by specific
comparison functions stored with the maps or in closures, but this
doesn't help me because deciding whether two trees represent the same
map is at least linear (but with a smaller N, there might be some
gain).  Actually, none of the available Bignum packages for O'Caml
supports polymorphic comparison.  Therefore I might have to make that
change soon.

BTW: how many unreleased symbolic math packages have been witten in
O'Caml?  I can't possibly be the first to discover how neatly one can
build rings from groups, algebras from modules, etc. using O'Caml's
module system ...  One of thy creators might explain why my
representation is a dumb idea!

Cheers,
-Thorsten
-- 
Thorsten Ohl, Physics Department, TU Darmstadt -- ohl@hep.tu-darmstadt.de
http://heplix.ikp.physik.tu-darmstadt.de/~ohl/ [<=== PGP public key here]