From mboxrd@z Thu Jan 1 00:00:00 1970 Received: (from majordomo@localhost) by pauillac.inria.fr (8.7.6/8.7.3) id OAA05060; Fri, 23 Apr 2004 14:51:44 +0200 (MET DST) X-Authentication-Warning: pauillac.inria.fr: majordomo set sender to owner-caml-list@pauillac.inria.fr using -f Received: from concorde.inria.fr (concorde.inria.fr [192.93.2.39]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id OAA05109 for ; Fri, 23 Apr 2004 14:51:43 +0200 (MET DST) Received: from pauillac.inria.fr (pauillac.inria.fr [128.93.11.35]) by concorde.inria.fr (8.12.10/8.12.10) with ESMTP id i3NCpfYM003526; Fri, 23 Apr 2004 14:51:41 +0200 Received: (from xleroy@localhost) by pauillac.inria.fr (8.7.6/8.7.3) id OAA05081; Fri, 23 Apr 2004 14:51:41 +0200 (MET DST) Date: Fri, 23 Apr 2004 14:51:41 +0200 From: Xavier Leroy To: Oliver Bandel Cc: caml-list@inria.fr Subject: Re: [Caml-list] Should be INSIDE STANDARD-LIB: Hashtbl.keys Message-ID: <20040423145141.B3686@pauillac.inria.fr> References: <20040421011904.GA1411@first.in-berlin.de> Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii X-Mailer: Mutt 1.0i In-Reply-To: <20040421011904.GA1411@first.in-berlin.de>; from oliver@first.in-berlin.de on Wed, Apr 21, 2004 at 03:19:04AM +0200 X-Miltered: at concorde by Joe's j-chkmail ("http://j-chkmail.ensmp.fr")! X-Loop: caml-list@inria.fr X-Spam: no; 0.00; caml-list:01 hashtbl:01 hash:01 quadratic:01 hashtbl:01 module:03 string:03 interface:03 library:03 library:03 behavior:03 behavior:03 rarely:03 data:03 data:03 Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk > I think a good addition to the Hashtbl-module > would be a function, that gives back a list of keys > that are in the hash. With your specification (no repetitions in the list), that function would run in quadratic time, which is a sure sign that lists aren't the right data structure here. (More generally speaking, "lists without repetitions" is almost always the wrong data structure.) If you shoot for decent efficiency, you have two choices: 1- a list of keys with possible repetitions, and 2- a set of keys. 1- is linear-time but rarely useful. 2- requires a suitable set module over the keys, and thus can't be done inside the Hashtbl library. As you see, there is no single "good" behavior and interface for the function you outline. (For another example, refer to the discussion about String.map earlier on this list; every poster had their own ideas about what type it should have.) That's a sign that it doesn't belong in the standard library, and you should program the behavior that you need in your application using Hashtbl.fold. - Xavier Leroy ------------------- 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