caml-list - the Caml user's mailing list
 help / color / mirror / Atom feed
* Re: [Caml-list] sorting Hashtbl.t
@ 2002-08-16 17:47 Brian Rogoff
  0 siblings, 0 replies; 9+ messages in thread
From: Brian Rogoff @ 2002-08-16 17:47 UTC (permalink / raw)
  To: caml-list; +Cc: skaller

Brian Rogoff writes:
> John Max Skaller writes:
> > > 	From an algorithmic point of view, there is no way to sort an
> > > hash table since there is no order attached to items. 
> [...snip extended Hashtbl interface ...]
> > Of course I can write this
> > function myself, it's just inconvenient to have to
> > keep doing so.

Sorry to follow up on my own message, but there is a way to do this kind of 
extension exactly once with only a tiny bit of clunkiness that I had missed
when I wrote the original flawed approach yesterday. So, I still disagree
that we need to provide module interfaces for things like hash tables,
though it's probably no harm to do so if lots of people agree that such
functions do belong in a basic interface. Thanks for making me think about
this! 

First, we create an extra signature in either the .ml and .mli files or in 
a third (.mli) file, like so 

(* hashtbl_sig.mli *) 
module type S = 
  sig
    type ('a, 'b) t = ('a, 'b) Hashtbl.t
    val create : int -> ('a, 'b) t
    val clear : ('a, 'b) t -> unit
    val add : ('a, 'b) t -> 'a -> 'b -> unit
    val copy : ('a, 'b) t -> ('a, 'b) t
    val find : ('a, 'b) t -> 'a -> 'b
    val find_all : ('a, 'b) t -> 'a -> 'b list
    val mem : ('a, 'b) t -> 'a -> bool
    val remove : ('a, 'b) t -> 'a -> unit
    val replace : ('a, 'b) t -> 'a -> 'b -> unit
    val iter : ('a -> 'b -> unit) -> ('a, 'b) t -> unit
    val fold : ('a -> 'b -> 'c -> 'c) -> ('a, 'b) t -> 'c -> 'c
  end

this signature exists just to remove the offending Make from the include,
and to create the type equality. The rest is easy 

(* exthash.mli *)
include Hashtbl_sig.S (* Remove the functorial interface *)
    
(* Module extension part *)
val elements : ('a, 'b) t -> 'b list

module type S = 
  sig 
    include Hashtbl.S 
    val elements : 'a t -> 'a list
  end

module Make (H : Hashtbl.HashedType) : S with type key = H.t

(* exthash.ml *)
include (Hashtbl : Hashtbl_sig.S)

let elements ht = 
  let r = ref [] in 
  (Hashtbl.iter (fun _ y -> r := y::(!r)) ht; !r)  

module type S = 
  sig 
    include Hashtbl.S 
    val elements : 'a t -> 'a list
  end

module Make (H : Hashtbl.HashedType) : S with type key = H.t = 
  struct 
    module Hashtbl =  Hashtbl.Make(H)
    include Hashtbl
    let elements ht = 
      let r = ref [] in 
      (Hashtbl.iter (fun _ y -> r := y::(!r)) ht; !r)  
  end

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


^ permalink raw reply	[flat|nested] 9+ messages in thread
* [Caml-list] sorting Hashtbl.t
@ 2002-08-12  1:08 Oleg
  2002-08-12  9:51 ` Nicolas Cannasse
  2002-08-12 10:10 ` Yann Régis-Gianas
  0 siblings, 2 replies; 9+ messages in thread
From: Oleg @ 2002-08-12  1:08 UTC (permalink / raw)
  To: caml-list

Hi

Hashtbl.iter does not always iterate in an orderly fashion, for instance

let h = Hashtbl.create 3 in 
for i = 1 to 10 do 
   Hashtbl.add h i i 
done; 
Hashtbl.iter (Printf.printf "%d, %d\n") h;;

Produces:
7, 7
8, 8
1, 1
9, 9
2, 2
10, 10
3, 3
4, 4
5, 5
6, 6

Is there any way to sort Hashtlb.t or otherwise make Hashtbl.iter iterate 
elements in order [1]?

Thanks
Oleg

[1] One could of course copy elements to a list or an array, then sort and 
iterate the latter, but I suppose it is inefficient, as hash table elements 
are "almost sorted".
-------------------
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


^ permalink raw reply	[flat|nested] 9+ messages in thread
end of thread, other threads:[~2002-08-16 17:47 UTC | newest]

Thread overview: 9+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2002-08-16 17:47 [Caml-list] sorting Hashtbl.t Brian Rogoff
  -- strict thread matches above, loose matches on Subject: below --
2002-08-12  1:08 Oleg
2002-08-12  9:51 ` Nicolas Cannasse
2002-08-12 13:44   ` Oleg
2002-08-13  7:45     ` Igor I. Harzmann
2002-08-12 10:10 ` Yann Régis-Gianas
2002-08-14 22:16   ` John Max Skaller
2002-08-14 23:13     ` Alexander V.Voinov
2002-08-15 16:43     ` Brian Rogoff

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).