Demo idea: Hashable interface with parallelizable associative hash function

[duvenaud]

It's useful to be able to hash any data structure, and it should be straightforward to allow this using Dex's typeclass system. Haskell has a comprehensive Hashable typeclass, for example.

But rather than just copying Haskell's implementation, there's a potential for Dex's implementation to take advantage of parallelism and the Accum effect. The only catch is that we'd have to find an associative hashing operation.

Luckily, one was recently developed: Hashing with SL2

Here's a Haskell implementation, which wraps C code and uses lots of unsafePerformIO. I expect that a Dex version could be much shorter, more portable and GPU friendly, and probably also allow more parallelism within chunks.

To get started, below is the beginning of an interface. The main idea is that an associative hash would allow the sequential fold for the table instance could be replaced with a parallel reduce.

interface Hashable a
  hash : Key -> a -> Key

instance Hashable Int32
  hash = \key y.
    y64 = IToW64 y
    threeFry2x32 key y64

instance Hashable Float32
  hash = \key y.
    y64 = IToW64 $ FToI y
    threeFry2x32 key y64

instance Hashable (Fin n)
  -- Todo: This should be the instance for the Idx typeclass.
  hash = \key y.
    y64 = IToW64 (ordinal y)
    threeFry2x32 key y64

instance [Hashable a] Hashable (Maybe a)
  hash = \key x. case x of
    Nothing -> hash (IToW64 0) 0
    Just x  -> hash (IToW64 1) x

instance [Hashable a] Hashable (n=>a)
  hash = \key table.
    fold key \i k. hash k table.i

instance [Hashable a, Hashable b] Hashable (a & b)
  hash = \key (left, right).
    hash (hash key left) right

instance [Hashable a, Hashable b] Hashable (a | b)
  hash = \key lor. case lor of
    Left  lor -> hash (IToW64 0) lor
    Right lor -> hash (IToW64 1) lor

This blog post also gives a bit more background on the problem, and an alternative approach.