Version française
Home     About     Download     Resources     Contact us    

This site is updated infrequently. For up-to-date information, please visit the new OCaml website at

Browse thread
[Caml-list] Should be INSIDE STANDARD-LIB: Hashtbl.keys
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
Date: 2004-04-23 (12:51)
From: Xavier Leroy <xavier.leroy@i...>
Subject: Re: [Caml-list] Should be INSIDE STANDARD-LIB: Hashtbl.keys
> 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 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 Archives:
Bug reports: FAQ:
Beginner's list: