Support for freezing of containers about hashtables

[recursion-ninja]

I really hope that this is possible, because it is how I would like to use most O(1) lookup functions.

[0xd34df00d]

@gregorycollins what are your thoughts on this? If you think this is OK, I might take a look at actually implementing this.

[gregorycollins]

My thought is, I don't really know how to do it cleanly so I haven't implemented it yet, and the use case hasn't seemed compelling enough to make the work feel worth it. All of the data types need to be reworked for pure lookup, but you want to use the same lookup algorithms everywhere, so you either have to duplicate everything or use templating/code generation.

One possibility you could consider is just to newtype around hashtables in IO, and use unsafePerformIO to expose only the non-mutating functions. I'm sure the purists reading this thread are choking on their Yerba Matés by now.

[0xd34df00d]

The use case is to build the hash table kust once in ST and then use it in pure code just for lookups without having to wrap the pure code in a monad.

I actually think of something similar - a newtype wrapper and runST'ing the existing lookup function.

[gregorycollins]

The use case is to build the hash table kust once in ST and then use it in pure code just for lookups without having to wrap the pure code in a monad.

My point is that you can already do this, with unsafePerformIO. A newtype wrapper and maybe a build function would help make it safer though:

build
  :: HashTable h
  => Maybe Int   -- ^ size hint
  -> (h s k v -> ST s ())
  -> ST s (Pure.HashTable k v)

Pure.HashTable can just be a set of lambdas doing either runST or unsafePerformIO:

data HashTable k v = HashTable { _lookup :: k -> Maybe v, ... }

The extra safety comes from swapping out the STRef inside the HashTable objects so that the mutable table can no longer be used once the user function is finished. It probably requires a new typeclass method.

[gregorycollins]

P.S. runST wants a forall s . ST s a, which you won't be able to give it -- your hashtable will have a concrete state type s. So here the only thing that will make it work is s=RealWorld and using unsafePerformIO anyways, the build function has to be:

build
  :: HashTable h
  => Maybe Int
  -> (IOHashTable h k v -> IO ())
  -> IO (Pure.HashTable k v)