On Mon, Aug 23, 2004 at 06:52:19PM -0500, Brian Hurt wrote:
> On Mon, 23 Aug 2004, Jesse Guardiani wrote:
> > Hello,
> > Could someone tell me how I might implement a
> > linkedhashtbl (or something similar) without
> > using a dllist?
> > I've become a bit disenchanted with dllist safety,
> > but I'm not familiar enough with the Map module
> > or any other possible alternatives to see any other
> > way to get the job done.
> I've been thinking about this a little bit too. My functional FIFO module
> doesn't work as you can't delete nodes from the middle of the fifo- only
> the head. My functional array code won't work either, as there is no
> "token" to be able to find the object in funcarr to delete it later.
> The easiest way to do this would be to make a map with integer keys, and
> then rebuild the entire data structure on index roll over. But the
> problem with this is that you need to be able to find the first key- a
> capability not present in the standard map module.
*Ahem*... I noticed this in ocaml-3.08.0:
val iter : (key -> 'a -> unit) -> 'a t -> unit iter f
m applies f to all bindings in map m. f receives the key
as first argument, and the associated value as second
argument. The bindings are passed to f in increasing order
with respect to the ordering over the type of the keys.
(Note that last bit).
So technically you can find the first key, by giving
YourMap.iter the function (fun k _ -> raise Found k) and
then catching the exception. It might be hideously
inefficient (not sure about the efficiency of exception
handling in OCaml), but it can be done. :)
I've actually wondered why Map doesn't have a lot of the
operations which exist for Set (but "applied" to the keys
as it were, i.e. min_key, max_key, ...), especially since
both Map.iter and Set.iter are now specified as presenting
the keys in a certain order (which basically narrows the
imlementations of both to be some sort of tree-like
structure which can support the same operations "on the
When your best just isn't good enough.