Re: [PATCH] Add-native-hashtable-helper-functions

[Nala Ginrut]

hi Daniel!
First, I'll appreciate your patience. ;-) 

On Wed, 2013-03-27 at 16:55 +0800, Daniel Hartwig wrote:
> On 27 March 2013 14:32, Nala Ginrut <address@hidden> wrote:
> > On Wed, 2013-03-27 at 13:10 +0800, Daniel Hartwig wrote:
> >> On 27 March 2013 08:47, Nala Ginrut <address@hidden> wrote:
> >> >
> >> > 在 2013-3-27 AM5:59，"Ludovic Courtès" <address@hidden>写道：
> >> >
> >> >
> >> >>
> >> >> Nala Ginrut <address@hidden> skribis:
> >> >>
> >>
> >> Hi now
> >>
> >> >> > * hash-items: get the amount of items in the hash table
> >> >>
> >> >> There’s already ‘hash-count’, recently added.
> >> >>
> >> >
> >> > If I need to check the amount of items
> >> > each time in the loop, hash-count will do redundant visit for all items. 
> >> > But
> >> > hash-items is efficient.
> >> >
> >>
> >> If you refer back to the thread discussing this, a constant time count
> >> of items was rejected in favour of the more general operator, and even
> >> that is provided only as a convenience.  That a constant time count of
> >> items is available is an implementation detail.  It is generally
> >> undesirably to expose such details.
> >>
> >
> > Well, could you point me out how can I get the amount of items with
> > hash-count in constant time?
> 
> No.  I offer only the vague notion that if this is critical to a
> program or some part, it is time to seriously reexamine the design of
> that.
> 
> The concept of “number of items” is not well defined for
> dictionaries.  Do you currently mean:
> 
> - number of key–value associations;
> - number of unique key–value associations;
> - number of unique values;
> - number of unique keys.
> 
> The answer changes depending on the task at hand.  The ability to
> compute any of those numbers varies wildly amongst the possible
> implementations.  As an internal detail of the _current_
> ‘make-hash-table’ in Guile, the first, second, and forth definition
> are equivalent and can be determined in constant time.  For alist
> and vhash, none of those are equivalent.
> 
> In the previous discussion, the motivating example used ‘hash-count’
> to test for a condition in a way that was simultaneously unreliable
> and difficult to verify.  Refactoring to avoid that would certainly
> yield an algorithm without one or the other of those undesirable
> traits.  Though I only made a solitary and rough attempt at
> demonstrating this, the revised design had a better worse-case
> complexity and was reliable.
> 
> An other, less “essential” use was completely superficial:
> 
>  (if (not (zero? (hash-count (identity #t) t)))
>      (hash-for-each proc t))
> 

All right, I found this string in the manual:
---------------------------cut-----------------------
To quickly determine the total number of elements, 
use `(const #t)' for PRED.
---------------------------end-----------------------

So we don't need hash-items anymore. ;-P
And sorry for bother since it's too new that I don't familiar with it.
Since it's in-explicit for such a function, how about add:

(define (hash-items ht) (hash-count (const #t) ht))


> which, except for any time spent counting, is equivalent to:
> 
>  (hash-for-each proc t)
> 
> > IMO, return the count of inner record is most explicit way.
> >
> >> The two fundamental queries on dictionary types are: extract the value
> >> associated with a given key; and iterate over all key–value pairs.
> >> Algorithms where hash-count is a critical operation (e.g. run inside a
> >> loop) are poorly designed, and not something to be encouraged by
> >> providing constant-time guarantees on that in the API.  A
> >> well-designed API encourages sound algorithm design by the interfaces
> >> it _omits_ just as much those it includes.  Here the goal is to expose
> >> an interface to the abstract data type, not any particular
> >> implementation. (Yes, some details are naturally leaked e.g. alist
> >> structure, but this is not a justification to leak even more.)
> >>
> >
> > Yes I won't against assoc & iterate are the most common operations.
> > But as an user who writing programs with Guile, people can't just use
> > the most common operations. They need more helpful things to alleviate
> > the workload. Though we can write all things with most common
> > operations, that's terrible for a practical programming.
> > That just like to say, I gave you all the bricks and cement, build
> > whatever you want, but don't ask for anything extra can be built with
> > bricks and cement.
> 
> For these particular procedures, I would put it more like:
> 
>  we do not supply those because all they do is shoot your feet.
> 
> >
> > And even our aim is to provide a clean and elegant language
> > implementation, but if it's too clean and elegant, it's only for
> > appreciation, not using.
> >
> > I'm not forcing to add my hash-items or hash-size, but I have to call
> > for any implementation for these two things, and I wish they add into
> > the core.
> 
> Alas, not just _any_ implementation can provide these.  By coincidence,
> _one_ of Guile's can, but do not be fooled: this is not useful
> information for an application to have.  If your application needs (?)
> this to perform well, or to function at all, there is a much better
> way to achieve the same result.  Guaranteed.
> 
> Likewise for ‘hash-keys’.
> 
> Perhaps you like to point out some code where you feel this is
> essential?
> 

Well, I can't say hash-keys is very common though I used it. I suggest
add it just because I found Racket has it. That makes me guess it's
common for others.

And for hash-size, I know a way to detect it with hash-count, since our
native hash-table size grows according to a given "steps table".
I suggest it because I thought users can't get this info unless guile
core export it.

> Regards