functional hash operations

functional hash operations

[Paul Jarc]

Sometimes it would be useful to have functional operations on hashes:
"make a copy of this hash which also has this additional entry", etc.
It would also be nice to make such copies share as much memory as
possible with the original hash.  This is easy enough to do by taking
advantage of the knowledge of the representation of hashes as vectors
of alists, but is it safe to assume that representation?  Or might the
representation change in the future?


paul


_______________________________________________
Guile-user mailing list
Guile-user@gnu.org
http://mail.gnu.org/mailman/listinfo/guile-user

Re: functional hash operations

[Thien-Thi Nguyen]

   From: prj@po.cwru.edu (Paul Jarc)
   Date: Mon, 30 Dec 2002 18:29:38 -0500

   "make a copy of this hash which also has this additional entry", etc.
   It would also be nice to make such copies share as much memory as
   possible with the original hash.

check out (ice-9 hcons).

   Or might the representation change in the future?

it all depends on who does the representing, so it's probably a good
idea to make sure you can influence those whose choices you want to rely
on (e.g., i'm still working on myself :-).  not relying is indicated.

thi


_______________________________________________
Guile-user mailing list
Guile-user@gnu.org
http://mail.gnu.org/mailman/listinfo/guile-user

Re: functional hash operations

[Paul Jarc]

Thien-Thi Nguyen <ttn@giblet.glug.org> wrote:
>    From: prj@po.cwru.edu (Paul Jarc)
>    Date: Mon, 30 Dec 2002 18:29:38 -0500
>
>    "make a copy of this hash which also has this additional entry", etc.
>    It would also be nice to make such copies share as much memory as
>    possible with the original hash.
>
> check out (ice-9 hcons).

I don't see how that will help me here.  I want something like:
(define (hash-add table key val)
  (let ((new-table (list->vector (vector->list table)))
        (index (hash key (vector-length table))))
    (vector-set! new-table index `((,key . ,val) . ,(vector-ref table index)))
    new-table))

This shares the keys, the values, the association pairs, and the list
pairs between the two tables.  (BTW, is there a better way to copy a
vector?)

Actually, I'm already writing my own constructors now, and it's easy
enough to reimplement the accessors too; I could avoid the built-in
hash functions altogether (other than hash itself).  As long as I'm at
it, I might as well create the new tables with more appropriate sizes
when they become full.  Is there any convenient way to compute a good
table size, given the number of entries?


paul


_______________________________________________
Guile-user mailing list
Guile-user@gnu.org
http://mail.gnu.org/mailman/listinfo/guile-user

Re: functional hash operations

[Christopher Cramer]

On Tue, Dec 31, 2002 at 04:26:53PM -0500, Paul Jarc wrote:
> (define (hash-add table key val)
>   (let ((new-table (list->vector (vector->list table)))
>         (index (hash key (vector-length table))))
>     (vector-set! new-table index `((,key . ,val) . ,(vector-ref table index)))
>     new-table))
> 
> This shares the keys, the values, the association pairs, and the list
> pairs between the two tables.  (BTW, is there a better way to copy a
> vector?)

A better way would be to use vector-move-left! or vector-move-right!:

(define (vector-copy v)
    (let* ((len (vector-length v)) (new (make-vector len)))
	(vector-move-left! v 0 len new 0)
	new))

But I hope you aren't copying a hash table in time-critical code to
begin with.

-- 
Christopher Cramer <crayc@pyro.net> <http://www.pyro.net/~crayc/>
"All you have to do is tell them they are being attacked and denounce the
pacifists for lack of patriotism and exposing the country to danger. It
works the same way in any country." - Hermann Georing, 1946


_______________________________________________
Guile-user mailing list
Guile-user@gnu.org
http://mail.gnu.org/mailman/listinfo/guile-user

Re: functional hash operations

[Paul Jarc]

Christopher Cramer <crayc@pyro.net> wrote:
> On Tue, Dec 31, 2002 at 04:26:53PM -0500, Paul Jarc wrote:
>> (BTW, is there a better way to copy a vector?)
>
> A better way would be to use vector-move-left! or vector-move-right!:

Looks good, thanks.

> But I hope you aren't copying a hash table in time-critical code to
> begin with.

I'm not planning to.  But even if I do, I only copy the vector this
way.


paul


_______________________________________________
Guile-user mailing list
Guile-user@gnu.org
http://mail.gnu.org/mailman/listinfo/guile-user

Re: functional hash operations

[Christopher Cramer]

On Mon, Dec 30, 2002 at 06:29:38PM -0500, Paul Jarc wrote:
> Sometimes it would be useful to have functional operations on hashes:
> "make a copy of this hash which also has this additional entry", etc.
> It would also be nice to make such copies share as much memory as
> possible with the original hash.  This is easy enough to do by taking
> advantage of the knowledge of the representation of hashes as vectors
> of alists, but is it safe to assume that representation?  Or might the
> representation change in the future?

It's hard for me to imagine any other good representation, so I don't
think it will change. OTOH if you want more operations on hash tables
it might not be a bad idea to get them included in Guile.

-- 
Christopher Cramer <crayc@pyro.net> <http://www.pyro.net/~crayc/>
"All you have to do is tell them they are being attacked and denounce the
pacifists for lack of patriotism and exposing the country to danger. It
works the same way in any country." - Hermann Georing, 1946


_______________________________________________
Guile-user mailing list
Guile-user@gnu.org
http://mail.gnu.org/mailman/listinfo/guile-user

Re: functional hash operations

[Marius Vollmer]

prj@po.cwru.edu (Paul Jarc) writes:

> Sometimes it would be useful to have functional operations on hashes:
> "make a copy of this hash which also has this additional entry", etc.
> It would also be nice to make such copies share as much memory as
> possible with the original hash.  This is easy enough to do by taking
> advantage of the knowledge of the representation of hashes as vectors
> of alists, but is it safe to assume that representation?  Or might the
> representation change in the future?

The hash table implementation should be considered opaque (except for
the handles) and if you want to play it safe, you should only use the
procedures from the reference manual with them.

Would it be workable to implement functional hash tables from scratch,
without basing them on the builtin implementation?  There are the
functions 'hash', 'hashv', and 'hashq' to help with computing hash
values for Scheme objects.

Or, as Thien-Thi has said, you can lobby the Guile developers to
include the things you need.  A working patch (also for the manual) is
quite convincing.

-- 
GPG: D5D4E405 - 2F9B BCCC 8527 692A 04E3  331E FAF8 226A D5D4 E405


_______________________________________________
Guile-user mailing list
Guile-user@gnu.org
http://mail.gnu.org/mailman/listinfo/guile-user

Re: functional hash operations

[Paul Jarc]

Marius Vollmer <mvo@zagadka.ping.de> wrote:
> Would it be workable to implement functional hash tables from scratch,
> without basing them on the builtin implementation?  There are the
> functions 'hash', 'hashv', and 'hashq' to help with computing hash
> values for Scheme objects.

I think this is what I'll do.  Given the number of associations in the
hash, how might I compute a good table size?  Finding a nearby prime
seems not too easy.  Are there other classes of numbers that also work
well?  Say, (2^n)-1 or (2^n)+1?


paul


_______________________________________________
Guile-user mailing list
Guile-user@gnu.org
http://mail.gnu.org/mailman/listinfo/guile-user