RFC: Adding a Hashable type class and HashMap/HashSet data types to HP

Antoine Latter aslatter at gmail.com
Fri Nov 26 15:07:43 EST 2010


On Fri, Nov 26, 2010 at 1:35 PM, Bryan O'Sullivan <bos at serpentine.com> wrote:
> On Thu, Nov 25, 2010 at 2:23 PM, Johan Tibell <johan.tibell at gmail.com>
> wrote:
>>
>> Is this an interesting problem to optimize for?
>
> I think so. The purpose of having the Hashable typeclass is so that the
> universe of typed values that we can hash is open. It thus behooves us to
> figure out how to do that safely. For instance, someone using the Hashable
> class should be able to figure out how to hash this:
> data HttpUrl = HttpUrl {
>   urlScheme :: ByteString,
>   urlHost :: ByteString,
>   urlPort :: Int,
>   urlPath :: ByteString,
>   urlQuery :: Maybe ByteString
>   }
> Using the Hashable class, I can see how to hash the individual elements of
> this, but not how to safely glue them together into a hash for the whole
> value.

I hope I'm not just stating the obvious -
My reflections on this thread, as someone who might have to write an
instance of 'Hashable' someday:

1. The design discussed in this thread puts the burden of choosing the
hashing algorithm onto the instance writer, every single time. This is
probably the correct choice, as it makes migration to a new algorithm
incremental and possible. And it means that data for which murmurhash
is inappropriate don't use it.

2. The above issue with the HttpUrl issue becomes much easier for me,
as an implementor, if solid instances for tuples are given. This
doesn't solve the underlying technical issue, but it does mean that we
only need to solve it once, and that library and application
implementors don't need to care about the solution (unless it doesn't
work well for some case).

My instances become mechanical translations into (tagged) tuples.

So I think I like the proposed interface, assuming that a good
instance for tuples is possible.

Antoine


More information about the Libraries mailing list