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
[Caml-list] Efficient and canonical set representation?
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
Date: 2003-11-07 (03:43)
From: Eray Ozkural <exa@k...>
Subject: Re: [Caml-list] Efficient and canonical set representation?
On Thursday 06 November 2003 18:41, Harrison, John R wrote:
> Does anyone know a representation of finite sets over an orderable
> polymorphic type that's (1) efficient and (2) canonical? Even better would
> be a CAML or OCaml implementation. More precisely I'm looking for:
>   1. Log-time lookup and insertion, and linear-time union, intersection
> etc.
>   2. Equal sets are represented by the same object.
> For example, ordered lists satisfy (2) but only part of (1), while all the
> variants of balanced trees I can remember that satisfy (1) --- AVL trees
> etc. --- fail (2).

It will be pretty hard to get 2. Not unless you are using disjoint sets :) You 
basically want O(1) for set equality, I suppose. Now, I think you wish to 
insert a new set in amortized O(lgn) time like in a disjoint set 

You can still use edison, isn't it good enough for you?

I'm saying this, because I don't think there is a straightforward functional  
way. I have on my mind 2-universal hash functions, but here I am facing bugs 
of my own. I'm not in the structure monster mode right now it seems :) 


Eray Ozkural (exa) <erayo@cs.bilkent.edu.tr>
Comp. Sci. Dept., Bilkent University, Ankara  KDE Project: http://www.kde.org
www: http://www.cs.bilkent.edu.tr/~erayo  Malfunction: http://mp3.com/ariza
GPG public key fingerprint: 360C 852F 88B0 A745 F31B  EA0F 7C07 AE16 874D 539C

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