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

[Daniel Hartwig]

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))

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?

Regards