[Caml-list] sorting Hashtbl.t

[Caml-list] sorting Hashtbl.t

[Oleg]

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

Re: [Caml-list] sorting Hashtbl.t

[Nicolas Cannasse]

> [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".

In general, Hashtbl are not "almost sorted", as one cannot garantee that
key(x) < key(y) => x < y.
If you want such a behavior, you should use a Binary Search Tree instead.

Nicolas Cannasse

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

Re: [Caml-list] sorting Hashtbl.t

[Yann Régis-Gianas]

On Sun, Aug 11, 2002 at 09:08:24PM -0400, Oleg wrote:
> Hi

	Hi,

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

	From an algorithmic point of view, there is no way to sort an
hash table since there is no order attached to items. Indeed, the
association is done through hash function that gives a fast-computable
signature to each key to find them quickly. (Re-)read the Cormen's book
to understand why you can't ask for such a feature ...

	Maybe you want Map.t that is an ordered associative structure ?



-- 
Yann Régis-Gianas.
-------------------
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

Re: [Caml-list] sorting Hashtbl.t

[Oleg]

On Monday 12 August 2002 05:51 am, Nicolas Cannasse wrote:
> > [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".
>
> In general, Hashtbl are not "almost sorted", as one cannot garantee that
> key(x) < key(y) => x < y.

I meant sorting by key (or iterating Hashtbl in the order of increasing 
_keys_).

> If you want such a behavior, you should use a Binary Search Tree instead.

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

Re: [Caml-list] sorting Hashtbl.t

[Igor I. Harzmann]

> > > as hash table elements are "almost sorted".
> >
> > In general, Hashtbl are not "almost sorted", as one cannot garantee that
> > key(x) < key(y) => x < y.
> 
> I meant sorting by key (or iterating Hashtbl in the order of increasing 
> _keys_).
> 

Hash table elements are _absolutely_ not sorted. It is the property of algorithm.

Sorry for poor english
-------------------
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

Re: [Caml-list] sorting Hashtbl.t

[John Max Skaller]

> 
> 	From an algorithmic point of view, there is no way to sort an
> hash table since there is no order attached to items. 


Ocaml has a polymorphic comparison function (which works
on all non-cyclic data structures). Therefore, any collection
of (non-cyclic) data elements can be sorted, and the request
actually makes sense. It is also something I wish to do
often.

However, I would ask for different function(s):

	Hastbl.to_list
	Hashtbl.to_lista
	Hashtbl.to_sorted_list compar
	Hashtbl.to_sorted_lista compar

which creates association list(s),

the standard version(s) producing
unique keys, and the 'a' version(s) an entry
for every element in the hashtable, with
duplicate keys in reverse order of entry into the table.
(so a sequential search finds the same value that a
Hashtbl.find would). Of course I can write this
function myself, it's just inconvenient to have to
keep doing so.

By the way: how can I make a hashtable that
uses addresses as keys? I.e. computes the hash
value on an address, not on a value.
(for collecting terms).

Hmmm. What happens if the key is a reference?

(or otherwise contains a mutable value?)



-- 
John Max Skaller, mailto:skaller@ozemail.com.au
snail:10/1 Toxteth Rd, Glebe, NSW 2037, Australia.
voice:61-2-9660-0850


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

Re: [Caml-list] sorting Hashtbl.t

[Alexander V.Voinov]

Hi 

From: John Max Skaller <skaller@ozemail.com.au>
Subject: Re: [Caml-list] sorting Hashtbl.t
Date: Thu, 15 Aug 2002 08:16:47 +1000

> 
> > 
> > 	From an algorithmic point of view, there is no way to sort an
> > hash table since there is no order attached to items. 
> 
> 
> Ocaml has a polymorphic comparison function (which works
> on all non-cyclic data structures). Therefore, any collection
> of (non-cyclic) data elements can be sorted, and the request
> actually makes sense. It is also something I wish to do
> often.
> 
> However, I would ask for different function(s):
> 
> 	Hastbl.to_list
> 	Hashtbl.to_lista
> 	Hashtbl.to_sorted_list compar
> 	Hashtbl.to_sorted_lista compar

I second this.

I've already defined something similar in a recent application, actually
equivalents of Python's .keys(), .values() and .items() with a subsequent sort
but I'd be happy with this interface as well.

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

Re: [Caml-list] sorting Hashtbl.t

[Brian Rogoff]

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.

The only thing that really prevents you from doing this just once in a 
fairly neat and comfortable way is the restriction on multiple definitions
of the same module name in a given structure or signature, in this case, 
Make. Why don't later module names just shadow previous ones, as later
function definitions follow succeeding ones? If this were the case, then we 
could handle this problem with something like so 

(* exthash.mli -- NOT LEGAL OCaml *)
include Hashtbl 

val elements : ('a, 'b) Hashtbl.t -> 'b list

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

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

(* exthash.ml -- NOT LEGAL OCaml *)
include Hashtbl 

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

module type S = 
  sig 
    include S (* S here refers to Hashtbl.S *)
    val elements : ('a, 'b) Hashtbl.t -> 'b list
  end

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

but because of the restrictions we need to replace those includes with a
manual copying of all of the relevant code from the Hashtbl module. 

-- 

  I mean, if 10 years from now, when you are doing something quick and dirty, 
  you suddenly visualize that I am looking over your shoulders and say to 
  yourself, 'Dijkstra would not have liked this,' well that would be enough 
  immortality for me.

  Edsger Wybe Dijkstra 1930-2002

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

Re: [Caml-list] sorting Hashtbl.t

[Brian Rogoff]

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