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

[Thomas Schilling]

This is what I had in mind: https://gist.github.com/717475

On 27 November 2010 00:28, Maciej Piechotka <uzytkownik2 at gmail.com> wrote:
> On Fri, 2010-11-26 at 23:05 +0000, Thomas Schilling wrote:
>> On 26 November 2010 17:18, Maciej Piechotka <uzytkownik2 at gmail.com> wrote:
>> > On Thu, 2010-11-25 at 16:15 +0000, Thomas Schilling wrote:
>> >> and for a data type with constructors C_1 .. C_n
>> >>
>> >>    2. hash (C_i x_i1 ... x_iN) = hash i <> hash x_i1 <> ... <> hash x_iN
>> >>
>> >> where <> is the hash combine function (probably (.))
>> >>
>> >
>> > (.) seems to fail type-checking.
>> >
>>
>> Right, sorry, I was actually having a different type in mind.  Something like:
>>
>>     newtype HashBuilder = HashBuilder { unHB :: Word -> Word }
>>     class Hashable a where
>>          addHash :: a -> HashBuilder
>>
>> The argument would be the seed.  We'd then have:
>>
>>     hash :: Hashable a => a -> Word
>>     hash a = finaliseHash $ unHB (addHash a) seed
>>        where
>>          seed = 0xdeadbeef
>>          finaliseHash x = ... -- some final mixing operation
>>
>> As Bryan mentioned, though, this does not allow building hashes in
>> parallel.  It would also hard-code the hash function.
>>
>
> Possibly the autogenerated function would be:
>
> hash (C_n x_1 x_2 ... x_n)
>    = hash "C_n" <> hash x_1 <> hash x_2 <> ... <> hash x_n
>
> where <> is function Word -> Word -> Word (like xor).
>
> Regards
>
> PS. As with list there is problem with hash "[]" and hash ":" possibly:
>
> instance Hashable a => Hashable [a] where
>    hash = foldl' (<>) 0xdeadbeef . map hash
>



-- 
Push the envelope. Watch it bend.