[m-rev.] for review: rationalise hash functions across the standard library

[Zoltan Somogyi]

On Tue, 11 Feb 2020 14:19:22 +1100 (AEDT), Julien Fischer <jfischer at opturion.com> wrote:
> I don't have any objections to moving to unsigned integers.  I would
> like whatever we end up with to be a little more well thought out
> than what's currently present in the library. 

Agreed.

> Perhaps, we should move
> to have hashable type class?

Perhaps, but that should be a separate change.

Are you thinking of adding this as a typeclass constraint to the signature
of all the hash table operations, or just doing this to the init function,
and having it stash the hash function in the hash_table structure,
as we now do with the hash predicate? The former seems cleaner,
the latter has a simpler correctness argument for the proposition
that all call sites use the same typeclass instance and hence the same
hash function.

> > The original implementation required two hash values.
> 
> Ah, that explains it!

I was curious what the two hash values were, so I had a look. While doing
that, I found something else. This:

:- type hash_table_alist(K, V)
    --->    ht_nil
    ;       ht_single(K, V)
    ;       ht_cons(K, V, hash_table_alist(K, V)).

While having ht_single as a special case is justifiable at the top level,
it is *not* justifiable in the third arg of ht_cons, since (a) it allows
more than one representation of the same data, and (b) it requires
a three-way choice, not a two-way choice, at each element.
(I actually had a slide showing how to avoid this when I taught
logic programming.)

I would replace ht_cons with something like

ht_more(K, V, K, V, kvlist(K, V)),

where kvlist is defined by

:- type kvlist(K, V)
    --->    kv_nil
    ;    kv_cons(K, V, kv_list(K, V)).

> > When I changed it to require only one hash value, I didn't change the
> > hash predicates to functions.
> 
> I have no objection to changing it to a function; we should be able to
> add wrappers that also preserve the existing interface.

I don't see much point in changing to functions; predicates work just
as well.

I think that this switch should be done, if at all, when we also switch
to that hashable typeclass. Two improvements, with just one disruption.

Zoltan.