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

[Julien Fischer]

On Tue, 11 Feb 2020, Zoltan Somogyi wrote:

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

Definitely.  The purpose of this change was to remove the code
duplication and deprecate some slightly dodgy things.

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

TBH, I hadn't thought that far ahead when I suggested it.
I'll sketch out a more concrete proposal.

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


I take it this was one motivation for your recent addition of such a
type ;-)

Julien.