Getting an element of a hashtable: simple ... or is it?

Getting an element of a hashtable: simple ... or is it?

[Brighten Godfrey]

Hi,

Suppose you are given a data structure, and you want to retrive one  
element -- any one element.  Sounds simple... and it is, if you have  
a list (List.hd list) or an array (arr.(0)).  But how about a  
hashtable, if we don't know a priori any of the keys in the hashtable?

The best way I've thought of so far is to begin iterating through all  
the hashtable's elements, but then break out with an exception:

exception Done
let get_one ht =
     let el = ref None in
     (try (
         Hashtbl.iter (fun i _ ->
             el := Some i;
             raise Done)
             ht;
         )
     with Done -> ());
     match !el with
         None -> raise Not_found
         | Some x -> x


But this seems clumsy.  Any better ideas?

Thanks,
Brighten Godfrey

Re: [Caml-list] Getting an element of a hashtable: simple ... or is it?

[Richard Jones]

On Tue, Aug 05, 2008 at 05:05:46AM -0700, Brighten Godfrey wrote:
> Suppose you are given a data structure, and you want to retrive one  
> element -- any one element.  Sounds simple... and it is, if you have  
> a list (List.hd list) or an array (arr.(0)).  But how about a  
> hashtable, if we don't know a priori any of the keys in the hashtable?

It's very unclear what you're trying to do.

For List and Array those methods won't work if the data structure is
empty, but I guess that's expected.  Hashtbl isn't designed with the
"get an/any element" usage in mind -- your loop/exception is probably
the best way given that you've made a poor choice of data structure in
the first place.  But this still comes back to the question, what are
you trying to do?

Rich.

-- 
Richard Jones
Red Hat

Re: [Caml-list] Getting an element of a hashtable: simple ... or is it?

[Brighten Godfrey]

On Aug 5, 2008, at 5:16 AM, Richard Jones wrote:

> On Tue, Aug 05, 2008 at 05:05:46AM -0700, Brighten Godfrey wrote:
>> Suppose you are given a data structure, and you want to retrive one
>> element -- any one element.  Sounds simple... and it is, if you have
>> a list (List.hd list) or an array (arr.(0)).  But how about a
>> hashtable, if we don't know a priori any of the keys in the  
>> hashtable?
>
> It's very unclear what you're trying to do.

I think you've interpreted me correctly.  I want a function that,  
given a hashtable, returns any element of the hashtable (assuming  
it's not empty).  This is the same as the function "choose" in the  
Set module.

> For List and Array those methods won't work if the data structure is
> empty, but I guess that's expected.  Hashtbl isn't designed with the
> "get an/any element" usage in mind -- your loop/exception is probably
> the best way given that you've made a poor choice of data structure in
> the first place.  But this still comes back to the question, what are
> you trying to do?

A hashtable is not a poor choice of a data structure, because this  
"choose" functionality is not the only requirement for my data  
structure: I also want constant time search.  OCaml's Set data  
structure has O(log n)-time search.

Thanks,
~Brighten

Re: [Caml-list] Getting an element of a hashtable: simple ... or is it?

[blue storm]

[-- Attachment #1: Type: text/plain, Size: 134 bytes --]

With Extlib you can use :
let get_one hashtbl = Enum.peek (Hashtbl.enum hashtbl)
val get_one : ('a, 'b) Hashtbl.t -> ('a * 'b) option

[-- Attachment #2: Type: text/html, Size: 182 bytes --]

Re: [Caml-list] Getting an element of a hashtable: simple ... or is it?

[Brighten Godfrey]

On Aug 5, 2008, at 5:25 AM, blue storm wrote:
> With Extlib you can use :
> let get_one hashtbl = Enum.peek (Hashtbl.enum hashtbl)
> val get_one : ('a, 'b) Hashtbl.t -> ('a * 'b) option

Ah, thanks.


On Aug 5, 2008, at 6:21 AM, Peng Zang wrote:
> I think this is pretty standard.  At least, I see it in ExtLib and  
> I do it on
> a regular basis.  In fact I have a function to do this for me so I  
> don't have
> to do it over and over again.  Eg.
>
>   let get_one ht = mkGetOne Hashtbl.iter ht

OK -- so you're saying ExtLib also implements it by breaking out of  
the loop with an exception.  Interesting.


On Aug 5, 2008, at 2:02 PM, Chris Kauffman wrote:
> I'm curious what sort of scenario calls for retrieving any single
> element of a hash table (which is potentially empty?). It seems most
> of the cases I deal with involve simply storing or iterating over all
> the elements.

Yes, nearly all cases are like that for me too.  But in this case, I  
want to decompose a graph into its connected components, roughly  
according to the following pseudocode:

     unprocessed_nodes : (node_t, unit) Hashtbl.t = all nodes
     while unprocessed_nodes not empty do
         let one_node = choose any one node from unprocessed_nodes
         let cc = find_connected_component_containing one_node
         Do some sort of processing on cc. Then:
         for each node v in cc
             remove v from unprocessed_nodes
         done

Thanks,
~Brighten Godfrey

Re: [Caml-list] Getting an element of a hashtable: simple ... or is it?

[Ludovic Coquelle]

If the type of hashtbl key is known (if the hashtbl module has been
created by the functor),
the same code as initial can avoid a reference and use exception
propagation mechanism:

type key = MyHashtbl.key
exception One of key
let get_one h = try (MyHashtbl.iter (fun k _ -> raise (One k)) h;
raise Not_found) with One x -> x

Can't we have polymorphic exception? like
'a exception One of 'a


On Wed, Aug 6, 2008 at 5:47 AM, Brighten Godfrey <pbg@cs.berkeley.edu> wrote:
> On Aug 5, 2008, at 5:25 AM, blue storm wrote:
>>
>> With Extlib you can use :
>> let get_one hashtbl = Enum.peek (Hashtbl.enum hashtbl)
>> val get_one : ('a, 'b) Hashtbl.t -> ('a * 'b) option
>
> Ah, thanks.
>
>
> On Aug 5, 2008, at 6:21 AM, Peng Zang wrote:
>>
>> I think this is pretty standard.  At least, I see it in ExtLib and I do it
>> on
>> a regular basis.  In fact I have a function to do this for me so I don't
>> have
>> to do it over and over again.  Eg.
>>
>>  let get_one ht = mkGetOne Hashtbl.iter ht
>
> OK -- so you're saying ExtLib also implements it by breaking out of the loop
> with an exception.  Interesting.
>
>
> On Aug 5, 2008, at 2:02 PM, Chris Kauffman wrote:
>>
>> I'm curious what sort of scenario calls for retrieving any single
>> element of a hash table (which is potentially empty?). It seems most
>> of the cases I deal with involve simply storing or iterating over all
>> the elements.
>
> Yes, nearly all cases are like that for me too.  But in this case, I want to
> decompose a graph into its connected components, roughly according to the
> following pseudocode:
>
>    unprocessed_nodes : (node_t, unit) Hashtbl.t = all nodes
>    while unprocessed_nodes not empty do
>        let one_node = choose any one node from unprocessed_nodes
>        let cc = find_connected_component_containing one_node
>        Do some sort of processing on cc. Then:
>        for each node v in cc
>            remove v from unprocessed_nodes
>        done
>
> Thanks,
> ~Brighten Godfrey
>
> _______________________________________________
> Caml-list mailing list. Subscription management:
> http://yquem.inria.fr/cgi-bin/mailman/listinfo/caml-list
> Archives: http://caml.inria.fr
> Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
> Bug reports: http://caml.inria.fr/bin/caml-bugs
>

Re: [Caml-list] Getting an element of a hashtable: simple ... or is it?

[Peng Zang]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

You can do something similar using options:

let getone h = 
  let res = ref None in
  try
    Hashtbl.iter (fun k v -> res := Some (k,v); raise Exit) h;
    !res
  with Exit -> !res
;;

Peng
  

On Friday 08 August 2008 11:46:41 am Ludovic Coquelle wrote:
> If the type of hashtbl key is known (if the hashtbl module has been
> created by the functor),
> the same code as initial can avoid a reference and use exception
> propagation mechanism:
>
> type key = MyHashtbl.key
> exception One of key
> let get_one h = try (MyHashtbl.iter (fun k _ -> raise (One k)) h;
> raise Not_found) with One x -> x
>
> Can't we have polymorphic exception? like
> 'a exception One of 'a
>
> On Wed, Aug 6, 2008 at 5:47 AM, Brighten Godfrey <pbg@cs.berkeley.edu> 
wrote:
> > On Aug 5, 2008, at 5:25 AM, blue storm wrote:
> >> With Extlib you can use :
> >> let get_one hashtbl = Enum.peek (Hashtbl.enum hashtbl)
> >> val get_one : ('a, 'b) Hashtbl.t -> ('a * 'b) option
> >
> > Ah, thanks.
> >
> > On Aug 5, 2008, at 6:21 AM, Peng Zang wrote:
> >> I think this is pretty standard.  At least, I see it in ExtLib and I do
> >> it on
> >> a regular basis.  In fact I have a function to do this for me so I don't
> >> have
> >> to do it over and over again.  Eg.
> >>
> >>  let get_one ht = mkGetOne Hashtbl.iter ht
> >
> > OK -- so you're saying ExtLib also implements it by breaking out of the
> > loop with an exception.  Interesting.
> >
> > On Aug 5, 2008, at 2:02 PM, Chris Kauffman wrote:
> >> I'm curious what sort of scenario calls for retrieving any single
> >> element of a hash table (which is potentially empty?). It seems most
> >> of the cases I deal with involve simply storing or iterating over all
> >> the elements.
> >
> > Yes, nearly all cases are like that for me too.  But in this case, I want
> > to decompose a graph into its connected components, roughly according to
> > the following pseudocode:
> >
> >    unprocessed_nodes : (node_t, unit) Hashtbl.t = all nodes
> >    while unprocessed_nodes not empty do
> >        let one_node = choose any one node from unprocessed_nodes
> >        let cc = find_connected_component_containing one_node
> >        Do some sort of processing on cc. Then:
> >        for each node v in cc
> >            remove v from unprocessed_nodes
> >        done
> >
> > Thanks,
> > ~Brighten Godfrey
> >
> > _______________________________________________
> > Caml-list mailing list. Subscription management:
> > http://yquem.inria.fr/cgi-bin/mailman/listinfo/caml-list
> > Archives: http://caml.inria.fr
> > Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
> > Bug reports: http://caml.inria.fr/bin/caml-bugs
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v2.0.7 (GNU/Linux)

iD8DBQFInG31fIRcEFL/JewRAm62AJ4yJzjMoxl+/uqOWubf90TNLBMeuQCfSktY
GYy2KGFGDXzxT36dHuBE0ks=
=bAf+
-----END PGP SIGNATURE-----

Re: [Caml-list] Getting an element of a hashtable: simple ... or is it?

[Peng Zang]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

I think this is pretty standard.  At least, I see it in ExtLib and I do it on 
a regular basis.  In fact I have a function to do this for me so I don't have 
to do it over and over again.  Eg.

  let get_one ht = mkGetOne Hashtbl.iter ht

Peng

On Tuesday 05 August 2008 08:05:46 am Brighten Godfrey wrote:
> Hi,
>
> Suppose you are given a data structure, and you want to retrive one
> element -- any one element.  Sounds simple... and it is, if you have
> a list (List.hd list) or an array (arr.(0)).  But how about a
> hashtable, if we don't know a priori any of the keys in the hashtable?
>
> The best way I've thought of so far is to begin iterating through all
> the hashtable's elements, but then break out with an exception:
>
> exception Done
> let get_one ht =
>      let el = ref None in
>      (try (
>          Hashtbl.iter (fun i _ ->
>              el := Some i;
>              raise Done)
>              ht;
>          )
>      with Done -> ());
>      match !el with
>          None -> raise Not_found
>
>          | Some x -> x
>
> But this seems clumsy.  Any better ideas?
>
> Thanks,
> Brighten Godfrey
>
> _______________________________________________
> Caml-list mailing list. Subscription management:
> http://yquem.inria.fr/cgi-bin/mailman/listinfo/caml-list
> Archives: http://caml.inria.fr
> Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
> Bug reports: http://caml.inria.fr/bin/caml-bugs
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v2.0.7 (GNU/Linux)

iD8DBQFImFPifIRcEFL/JewRAreVAKCOxjyr8uXNIOknO4zmL+i0La4RCQCcDLV1
OXN2V4ZiS8oxC5hQOf5phYU=
=ZXwI
-----END PGP SIGNATURE-----

Re: [Caml-list] Getting an element of a hashtable: simple ... or is it?

[Chris Kauffman]

I'm curious what sort of scenario calls for retrieving any single
element of a hash table (which is potentially empty?). It seems most
of the cases I deal with involve simply storing or iterating over all
the elements.

Cheers,
Chris