[m-rev.] for review: rationalise hash functions across the standard library
jfischer at opturion.com
Fri Feb 14 17:05:22 AEDT 2020
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.
>> 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
More information about the reviews