Version française
Home     About     Download     Resources     Contact us    
Browse thread
[Caml-list] sorting Hashtbl.t
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
Date: -- (:)
From: Brian Rogoff <bpr@a...>
Subject: Re: [Caml-list] sorting Hashtbl.t
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