Re: [Caml-list] Should be INSIDE STANDARD-LIB: Hashtbl.keys

[Jon Harrop <jdh30@cam.ac.uk>]

On Friday 23 April 2004 2:05 pm, Jean-Baptiste Rouquier wrote:
> >With your specification (no repetitions in the list), that function
> >would run in quadratic time,
>
> Perhaps I'm all wrong, but when I have to get rid of repetitions in a
> list, I first sort it in O(n log n), then remove the repetitions in O(n).
> Jean-Baptiste.

I have no idea what I'm talking about, but does this function not do what you 
want in O(n):

let hashtbl_keys tbl =
  let rec helper k d l = match l with
    [] -> [k]
  | ok::t -> if k=ok then l else k::l
  in
  Hashtbl.fold helper tbl []

because Hashtbl's iter and fold present duplicate keys subsequently?

Cheers,
Jon.

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