modifying hash tables

modifying hash tables

[Sam Steingold]

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

I want to modify the _current_ datum in Hashtable.iter, e.g., increment
a count. Is this code valid?
Hashtable.iter ht ~f:(fun ~key ~data ->
  Hashtable.replace ht ~key ~data:(data+1))
(it appears to work, but I was told that "it is not guaranteed to work",
i.e., the documentation does not promise that).
If the above code is wrong, what is TRT?
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.6 (GNU/Linux)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org

iD8DBQFGnjFxPp1Qsf2qnMcRAhFaAJ0WEo90RwF5e1Ue+0tCdLyW2R5gawCcCJfd
T8szhrihvlLwCh5L+er0N1E=
=9bhb
-----END PGP SIGNATURE-----

Re: [Caml-list] modifying hash tables

[Christopher L Conway]

Assuming that your question is "is it OK to modify a Hashtbl while you
iterate over it?" and assuming that the answer is "maybe, but maybe
not" and assuming that I am looking for a way to avoid doing real
work, you might try the following:

(Hashtbl.fold
   (fun key data f ->
     (fun ht -> Hashtable.replace ht key (data+1); f ht))
   ht
   (fun _ -> ()))
  ht

Chris

On 7/18/07, Sam Steingold <sds@gnu.org> wrote:
> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA1
>
> I want to modify the _current_ datum in Hashtable.iter, e.g., increment
> a count. Is this code valid?
> Hashtable.iter ht ~f:(fun ~key ~data ->
>   Hashtable.replace ht ~key ~data:(data+1))
> (it appears to work, but I was told that "it is not guaranteed to work",
> i.e., the documentation does not promise that).
> If the above code is wrong, what is TRT?
> -----BEGIN PGP SIGNATURE-----
> Version: GnuPG v1.4.6 (GNU/Linux)
> Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org
>
> iD8DBQFGnjFxPp1Qsf2qnMcRAhFaAJ0WEo90RwF5e1Ue+0tCdLyW2R5gawCcCJfd
> T8szhrihvlLwCh5L+er0N1E=
> =9bhb
> -----END PGP SIGNATURE-----
>
> _______________________________________________
> 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: modifying hash tables

[Sam Steingold]

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

Sam Steingold wrote:
> I want to modify the _current_ datum in Hashtable.iter, e.g., increment
> a count. Is this code valid?
> Hashtable.iter ht ~f:(fun ~key ~data ->
>   Hashtable.replace ht ~key ~data:(data+1))
> (it appears to work, but I was told that "it is not guaranteed to work",
> i.e., the documentation does not promise that).
> If the above code is wrong, what is TRT?

in case you wondered why I think my code is reasonable:
http://www.lisp.org/HyperSpec/Body/sec_3-6.html

Hash-table traversal

    For hash table traversal operations, new elements may not be added
or deleted except that the element corresponding to the current hash key
may be changed or removed.



(yes, I know OCaml is NOT Common Lisp).


-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.6 (GNU/Linux)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org

iD8DBQFGnjltPp1Qsf2qnMcRAhZDAJ9JLNLklo6tK+oGSd2ije172z+3+wCcDXyc
JRU8vSR/5cMBDeBTFjvSylg=
=Q5wE
-----END PGP SIGNATURE-----

Re: [Caml-list] Re: modifying hash tables

[Brian Hurt]

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

Sam Steingold wrote:

>-----BEGIN PGP SIGNED MESSAGE-----
>Hash: SHA1
>
>Sam Steingold wrote:
>  
>
>>I want to modify the _current_ datum in Hashtable.iter, e.g., increment
>>a count. Is this code valid?
>>Hashtable.iter ht ~f:(fun ~key ~data ->
>>  Hashtable.replace ht ~key ~data:(data+1))
>>(it appears to work, but I was told that "it is not guaranteed to work",
>>i.e., the documentation does not promise that).
>>If the above code is wrong, what is TRT?
>>    
>>
>
>in case you wondered why I think my code is reasonable:
>http://www.lisp.org/HyperSpec/Body/sec_3-6.html
>
>Hash-table traversal
>
>    For hash table traversal operations, new elements may not be added
>or deleted except that the element corresponding to the current hash key
>may be changed or removed.
>
>  
>
See also C++'s STL iterators.

The fundamental problem here is that more gaurantees you give as to how 
things work as you mutate data structures as you iterate over them, the 
less flexibility you have in how those data structures can be 
implemented.  At the extreme, you have the "one true implementation", 
which is the only legal implementation.  At the other extreme, you have 
no gaurentees what so ever as to what will happen when you modify a data 
structure while iterating over it.

Lisp chose one trade-off, C++ another, and Ocaml a third.

Brian


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

RE: [Caml-list] modifying hash tables

[David Allsopp]

> I want to modify the _current_ datum in Hashtable.iter, e.g., increment
> a count. Is this code valid?
> Hashtable.iter ht ~f:(fun ~key ~data ->
>   Hashtable.replace ht ~key ~data:(data+1))
> (it appears to work, but I was told that "it is not guaranteed to work",
> i.e., the documentation does not promise that).
> If the above code is wrong, what is TRT?

You're referring to module "Hashtable" - where's this from?

The potential problem is that you're changing the hash table while it's
being "read" - it's a matter of "definition" on what that sort of use means.
For example,

let t = Hashtbl.create 32
in
  Hashtbl.add t 1 "a"; Hashtbl.add t 2 "b"; Hashtbl.add t 3 "c";
  (* As it happens, these will print in order... *)
  Hashtbl.iter (fun k v -> Printf.printf "%d: %s\n" k v) t;
  (* Now let's mess around... *)
  let f k v =
    Printf.printf "%d: %s\n" k v;
    if k = 2
    then Hashtbl.remove t 3
  in
    Hashtbl.iter f t;;

prints three lines resulting from the initial iter but only two lines
resulting from the second iter yet the documentation for Hashtbl.iter states
"Hashtbl.iter f tbl applies f to all bindings in table tbl" - the definition
of "all bindings" is left somewhat fuzzy (probably on purpose!). Just to
make things weirder - if you re-run the code above but change the 32 to 3 in
the first line then all three bindings are printed twice because of the
different ordering of the elements in the hash table! You can get some even
"stranger" (by which I mean unpredictable) results if you come up with a
function that adds elements and so causes the table to be resized mid-way
through the iter...

	In your code, you're only replacing the data of existing bindings so
you're likely to be fine using iter (at least in the current implementation)
as the keys won't change - it's probably worthy of a big safety comment in
your code, though. "Safer" solutions include ExtLib's Hashtbl.ExtHashtbl.map
function or the Map module. Both of these have performance hits that may be
of concern - maps are on average slower than hash tables in O'Caml and
Hashtbl.map copies the table each time (though it's not clear to me why it
bothers doing that - it wouldn't take much to alter it to do an in-place
map).

	The "problem" as such is applying functional idioms such as fold and
iter to an inherently imperative data structure...


David

Re: modifying hash tables

[Zheng Li]

Sam Steingold <sds@gnu.org> writes:
> I want to modify the _current_ datum in Hashtable.iter, e.g., increment
> a count. Is this code valid?
> Hashtable.iter ht ~f:(fun ~key ~data ->
>   Hashtable.replace ht ~key ~data:(data+1))

If you have associate several datums with the same key, the semantic of the
code is to substitute the current binding of each key with the value of its
earliest binding plus one.

-- 
Zheng Li
http://www.pps.jussieu.fr/~li

Re: [Caml-list] modifying hash tables

[Jon Harrop]

On Wednesday 18 July 2007 16:27:45 Sam Steingold wrote:
> I want to modify the _current_ datum in Hashtable.iter, e.g., increment
> a count. Is this code valid?
> Hashtable.iter ht ~f:(fun ~key ~data ->
>   Hashtable.replace ht ~key ~data:(data+1))
> (it appears to work, but I was told that "it is not guaranteed to work",
> i.e., the documentation does not promise that).
> If the above code is wrong, what is TRT?

I would store "int ref"s in the hash table and use "incr".

-- 
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
OCaml for Scientists
http://www.ffconsultancy.com/products/ocaml_for_scientists/?e