From mboxrd@z Thu Jan  1 00:00:00 1970
Return-Path: <pbg@cs.berkeley.edu>
X-Spam-Checker-Version: SpamAssassin 3.1.3 (2006-06-01) on yquem.inria.fr
X-Spam-Level: *
X-Spam-Status: No, score=1.1 required=5.0 tests=AWL,SPF_SOFTFAIL 
	autolearn=disabled version=3.1.3
Received: from mail1-relais-roc.national.inria.fr (mail1-relais-roc.national.inria.fr [192.134.164.82])
	by yquem.inria.fr (Postfix) with ESMTP id F0F94BBAF
	for <caml-list@yquem.inria.fr>; Tue,  5 Aug 2008 14:33:03 +0200 (CEST)
X-IronPort-Anti-Spam-Filtered: true
X-IronPort-Anti-Spam-Result: AkcBAE7kl0ip5TxXo2dsb2JhbACROQEBAQEBAQcFCAcRnEo
X-IronPort-AV: E=Sophos;i="4.31,310,1215381600"; 
   d="scan'208";a="15821372"
Received: from gateway0.eecs.berkeley.edu ([169.229.60.87])
  by mail1-smtp-roc.national.inria.fr with ESMTP/TLS/DHE-RSA-AES256-SHA; 05 Aug 2008 14:26:39 +0200
Received: from [10.0.1.5] (136-152-208-5.VPN.Berkeley.EDU [136.152.208.5])
	(authenticated bits=0)
	by gateway0.EECS.Berkeley.EDU (8.14.3/8.13.5) with ESMTP id m75CQSuo000109
	(version=TLSv1/SSLv3 cipher=AES128-SHA bits=128 verify=NOT);
	Tue, 5 Aug 2008 05:26:30 -0700 (PDT)
In-Reply-To: <20080805121600.GB25452@annexia.org>
References: <94C5D65F-7CA4-48FF-B4AA-E88E82F6C8E1@cs.berkeley.edu> <20080805121600.GB25452@annexia.org>
Mime-Version: 1.0 (Apple Message framework v753.1)
Content-Type: text/plain; charset=US-ASCII; delsp=yes; format=flowed
Message-Id: <0A438E08-42BB-4CC9-889E-7AAF90323CC8@cs.berkeley.edu>
Cc: caml-list@yquem.inria.fr
Content-Transfer-Encoding: 7bit
From: Brighten Godfrey <pbg@cs.berkeley.edu>
Subject: Re: [Caml-list] Getting an element of a hashtable: simple ... or is it?
Date: Tue, 5 Aug 2008 05:26:27 -0700
To: Richard Jones <rich@annexia.org>
X-Mailer: Apple Mail (2.753.1)
X-Spam: no; 0.00; hashtable:01 hashtable:01 hashtbl:01 ocaml's:01 wrote:01 wrote:01 exception:01 caml-list:01 data:02 data:02 module:03 element:03 element:03 berkeley:04 guess:04 

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