Make use of `hashable`'s `Hashed` type?!

[sjakobi]

https://hackage.haskell.org/package/hashable-1.5.0.0/docs/Data-Hashable.html#t:Hashed

(Original discussion: haskell-unordered-containers/hashable#76)

How about adding

toHashedList :: HashMap k v -> [(Hashed k, v)]

fromUniqueHashedList :: [(Hashed k, v)] -> HashMap k v

This could be useful for the code pattern

HM.fromList <$> doStuff (HM.toList m)

(CC @andrewthad, who implemented the type in haskell-unordered-containers/hashable#121)

[andrewthad]

One problem with the proposed functions is that a hashmap will not round trip when there are collisions. This can be fixed by replacing the second function with:

fromHashedList :: Eq v => [(Hashed k, v)] -> HashMap k v

[sjakobi]

Ah, I think my fromUniqueHashedList was just badly named. It's not the hashes that are expected be unique, but the keys.

Would something like fromHashedListDistinctKeys be clearer? I think we can still get away without the Eq constraint, because we could use an unsafe version of insertNewKey to build the map.

unordered-containers/Data/HashMap/Internal.hs

Lines 850 to 857 in d06eb34

	-- | Insert optimized for the case when we know the key is not in the map.
	--
	-- It is only valid to call this when the key does not exist in the map.
	--
	-- We can skip:
	-- - the key equality check on a Leaf
	-- - check for its existence in the array for a hash collision
	insertNewKey :: Hash -> k -> v -> HashMap k v -> HashMap k v

[andrewthad]

Oh, I understand now. Yeah, if the function has a precondition that are no duplicate keys, then I agree that you should be able to avoid the Eq constraint. I like fromHashedListDistinctKeys as the name, and it also leaves open the possibility of a fromHashedList that does not have the same precondition.

There is some prior art in Data.Set, which uses names like fromDistinctAscList for this. The most consistent name with that one is fromDistinctHashedList, but that makes it sound too much like it's the hashes that are distinct. On the naming issue, I don't have a strong opinion. I'm not sure that anything is going to be great. But I think that the function itself makes sense to include in the library.

[treeowl]

Do we currently have functions that can break invariants? If not, I suggest adding .Unsafe modules for these.

[sjakobi]

IMHO Unsafe is kind of a big word for something like fromHashedListDistinctKeys.

Should Data.Map.fromAscList live in an .Unsafe module too then?!

[treeowl]

In my opinion, yes, it should. But moving it years after the fact would be disruptive.