[m-dev.] For review: hash table implementation

[Fergus Henderson]

On 05-Feb-2001, Ralph Becket <rbeck at microsoft.com> wrote:
> > > int_hash_pred =
> > >     ( pred(N::in, H1::out, H2::out) is det :-
> > >         H1 = N * N,
> > >         H2 = N `xor` (N + N)
> > >     ).
> > 
> > Why not just `H1 = N'?
> 
> I perceived (through highly unscientific testing) that this gave a
> better spread where N is small.  It's a weak justification, so I'll
> change it back if it offends people :)

No, that's probably better as is.
But adding a comment or two here might be nice.

> ----------------------------------------------------------------------------
> %
> 
>     % This, again, is straight off the top of my head.
>     %
> generic_double_hash(T, Ha, Hb) :-
>     (      if dynamic_cast(T, Int) then
>         int_double_hash(Int, Ha, Hb)
>       else if dynamic_cast(T, String) then
>         string_double_hash(String, Ha, Hb)
>       else if dynamic_cast(T, Univ) then
>         generic_double_hash(univ_value(Univ), Ha, Hb)
>       else if dynamic_cast(T, Array) then
>         {Ha, Hb} =
>             array__foldl(
>                 ( func(X, {HA0, HB0}) = {HA, HB} :-
>                     generic_double_hash(X, HXA, HXB),
>                     HA = munge(munge_factor_a, HA0, HXA),
>                     HB = munge(munge_factor_b, HB0, HXB)
>                 ),
>                 Array,
>                 {0, 0}
>             )

That won't work:

(1) there's no array__foldl in the current standard library.

(2) dynamic cast only works for casting to ground types,
    not for pattern matching with partially instantiated
    type patterns, e.g. `array(T)'.  Probably the compiler
    issued a warning for this.  Read the compiler warnings.
    Compile again with `-E' and read them again.

>       else
>         deconstruct(T, FunctorName, Arity, Args),
>         string_double_hash(FunctorName, Ha0, Hb0),
>         Ha1 = munge(munge_factor_a, Ha0, Arity),
>         Hb1 = munge(munge_factor_b, Hb0, Arity),
>         list__foldl2(
>             ( pred(U::in, HA0::in, HA::out, HB0::in, HB::out) is det :-
>                 generic_double_hash(U, HUA, HUB),
>                 HA = munge(munge_factor_a, HA0, HUA),
>                 HB = munge(munge_factor_b, HB0, HUB)

The two lines above are duplicated several times; it would be
nicer to extract the commonality out into a separate predicate
or function.

-- 
Fergus Henderson <fjh at cs.mu.oz.au>  |  "I have always known that the pursuit
                                    |  of excellence is a lethal habit"
WWW: <http://www.cs.mu.oz.au/~fjh>  |     -- the last words of T. S. Garp.
--------------------------------------------------------------------------
mercury-developers mailing list
Post messages to:       mercury-developers at cs.mu.oz.au
Administrative Queries: owner-mercury-developers at cs.mu.oz.au
Subscriptions:          mercury-developers-request at cs.mu.oz.au
--------------------------------------------------------------------------