Make HashMap interface compatible with Data.Map from containers

[m-renaud]

I've recently started contributing to containers and noticed that the interface for HashMap is slightly different in some spots or missing some functions compared to Data.Map. The ones I've noticed so far are:

Missing:

(Eq k, Hashable k) constraint applies for each.

• (!?) :: HashMap k v -> k -> Maybe v (Add operator HashMap.!? #175)
  • Flipped lookup
• keysSet :: HashMap k a -> HashSet k
• fromListWithKey :: (k -> a -> a -> a) -> [(k, a)] -> HashMap k a
• alterF :: (Maybe a -> f (Maybe a)) -> k -> HashMap k a -> f (HashMap k a)
• differenceWithKey :: (k -> v1 -> v2 -> v3) -> HashMap k v1 -> HashMap k v2 -> HashMap k v3

The following are unnecessary micro-optimizations or not pulling their weight and should be removed from containers:

adjustWithKey :: (k -> a -> a) -> k -> HashMap k a -> HashMap k a (#178)

insertWithKey :: (k -> a -> a -> a) -> k -> a -> HashMap k a -> HashMap k a (#177)

updateWithKey :: (k -> a -> Maybe a) -> k -> HashMap k a -> HashMap k a

notMember :: k -> HashMap k a -> Bool

IMHO the Data.Map API is too big, so there are others not present that I haven't included in the list.

Different:

• Data.Map.findWithDefault == Data.HashMap.lookupDefault (Add HashMap.findWithDefault #176)
  • I propose we deprecate lookupDefault in favour of findWithDefault (libraries thread)

If you agree these (or a subset of these) should be added I can put together some pull requests adding them. WDYT?

[treeowl]

I would prefer to remove the following from containers:

• insertWithKey
• updateWithKey
• findWithDefault

Like adjustWithKey, these are micro-optimizations. I'd really like to cut them out to streamline the API.

I would generally also prefer to remove notMember if the opposition isn't too strenuous.

The insertWith function I wish we had is

InsertFoo :: v -> (v -> v) -> k -> HashMap k v -> HashMap k v

or (better for lazy insertion, but annoying for strict insertion)

data Box a = Box a
insertBar :: v -> (v -> Box v) -> k -> HashMap k v -> HashMap k v
insertBar new f = insertBar# new (\old -> case f old of Box new -> (# new #))

The fromList I'd want is probably something like

fromListFoo :: (k -> a -> v) -> (k -> a -> v -> v) -> [(k, a)] -> HashMap k v
-- alternate version:
fromListFooMb :: (k -> a -> Maybe v -> v) -> [(k, a)] -> HashMap k v

or for the lazy version something like

fromListBar:: (k -> a -> Box v) -> (k -> a -> v -> Box v) -> [(k, a)] -> HashMap k v
-- alternate version:
fromListBarMb :: (k -> a -> Maybe v -> Box v) -> [(k, a)] -> HashMap k v

But we can't even think about adding such things until we start the process of trimming cruft.

[m-renaud]

I can get on board with that, I've scratched them off from the list. I'd much prefer trimming the containers API as well, but wasn't sure how feasible that would be given how core it is. I always wondered why notMember existed as well considering it's literally just not $ member ....

On first glance I think I prefer fromListFoo since it more clearly isolates concerns (1. how to create a v from a k and an a, 2. How to merge values if the key is already in the map). But as you say, we need to trim the API before even thinking about adding new stuff :)