Too restrictive type signatures

[Vlix]

I feel that at least the following functions should have less restrictive type signatures:
C) {current signature}
P) {proposed signature}

C) insertWith :: Ord k => (a -> a -> a) -> k -> a -> Map k a -> Map k a
P) insertWith :: Ord k => (a -> b -> b) -> k -> a -> Map k b -> Map k b
---
C) insertWithKey :: Ord k => (k -> a -> a -> a) -> k -> a -> Map k a -> Map k a
P) insertWithKey :: Ord k => (k -> a -> b -> b) -> k -> a -> Map k b -> Map k b
---
C) insertLookupWithKey :: Ord k => (k -> a -> a -> a) -> k -> a -> Map k a -> (Maybe a, Map k a)
P) insertLookupWithKey :: Ord k => (k -> a -> b -> b) -> k -> a -> Map k b -> (Maybe b, Map k b)

[treeowl]

While I agree the signatures are unfortunate, your proposed replacements simply won't work. Can you understand why? Try implementing them using insert and lookup.

[Vlix]

Ah, I've overlooked the case where it's just an insert instead of an "update".

Then I feel like another set of functions that "upsert" (update/insert) would be helpful. e.g.:
upsert :: Ord k => b -> (a -> b -> b) -> k -> a -> Map k b -> Map k b
upsert x f key newVal mp = ...
which would insert k x in case the key was absent and
insert k (f newVal oldVal)
in case the key already exists.

upsert :: Ord k => a -> (b -> a -> a) -> k -> b -> Map k a -> Map k a
upsert = go
  where
    go :: Ord k => a -> (b -> a -> a) -> k -> b -> Map k a -> Map k a
    go a _ !kx _ Tip = singleton kx a
    go a f !kx x (Bin sy ky y l r) =
        case compare kx ky of
            LT -> balanceL ky y (go a f kx x l) r
            GT -> balanceR ky y l (go a f kx x r)
            EQ -> Bin sy kx (f x y) l r

[treeowl]

I've been thinking the natural options are

whatever :: Ord k => b -> (b -> b) -> k -> Map k b -> Map k b
whatever' :: Ord k => (Maybe b -> b) -> k -> Map k b -> Map k b

[sjakobi]

Is there anything that ought to be addressed in this issue? Currently I'm a bit confused.

[treeowl]

@sjakobi, I think this is really just another instance of people complaining about how wretched the insertWith type is. Let's have a little conference and decide what to suggest to the libraries list. It's been long enough; time to bite the bullet and fix this mess.

[sjakobi]

@sjakobi, I think this is really just another instance of people complaining about how wretched the insertWith type is.

I actually wasn't aware that insertWith itself is so problematic. You have to know which value comes first in the parameters of the combining function, but that's about it, no?! For a bit more safety, people can use alter.

whatever' :: Ord k => (Maybe b -> b) -> k -> Map k b -> Map k b

I do like this type though. Maybe we should give the implementation in the documentation for alter (and reference it from insertWith)?!

I'm not opposed to exporting it either.

---

The issue of fromListWith (#333, haskell-unordered-containers/unordered-containers#264) is more grave IMHO since the behaviour is so counterintuitive. That it internally uses insertWith seems like an implementation detail to me though.

[treeowl]

Personally, I have to look up the insertWith documentation every single time I want to use it.

[sjakobi]

OK. I guess we can't change or get rid of insertWith though.

Is using alter directly good enough?

Otherwise we need a proposal for an addition – possibly with the mentioned Ord k => (Maybe b -> b) -> k -> Map k b -> Map k b type.

[treeowl]

Maybe so. Should we perform manual worker/wrapper with unboxed sums to try to improve alter performance? Higher-order worker/wrapper seems to be well beyond GHC's abilities.

[sjakobi]

Should we perform manual worker/wrapper with unboxed sums to try to improve alter performance? Higher-order worker/wrapper seems to be well beyond GHC's abilities.

My understanding of the optimizations that GHC can apply is unfortunately way too vague for me to give a useful response! :/

Is it important that we consider performance first though?

How about we try to nail the ergonomics first and then see whether more performance work is needed?!

(Also, is #523 related?!)

[treeowl]

The idea is that we can write

-- Unlifted newtypes exist now, right?
newtype Maybe# a = Maybe# (# (##) | a #)

pattern Nothing# :: Maybe# a
pattern Nothing# = Maybe# (# (##) | #)

pattern Just# :: a -> Maybe# a
pattern Just# v = Maybe# (# | v #)

alter :: Ord k => (Maybe a -> Maybe a) -> k -> Map k a -> Map k a
alter f = alter# $ \case
  Nothing# _ -> case f Nothing of
    Nothing -> Nothing#
    Just v -> Just# v
{-# INLINE alter #-}

alter# :: Ord k => (Maybe# a -> Maybe# a) -> k -> Map k a -> Map k a

The idea is that there's a good chance GHC will inline f and avoid producing any Maybes. But we do have to think carefully about some bits. For example, will an f Nothing thunk form unconditionally? Best if that doesn't happen.

[Vlix]

Kind of late, but I found this issue again and think that what I was looking for initially was something like:
insertWith :: Ord k => (a -> Maybe b -> b) -> k -> a -> Map k b -> Map k b
The idea being that the given function is always used, not just when updating, but also when inserting.

But I guess that's just a bit more specific alter, so not sure if it would be useful to add.

upsert :: Ord k => (a -> Maybe b -> b) -> k -> a -> Map k b -> Map k b
upsert f k newVal = alter (Just . f newVal) k

[sjakobi]

@Vlix Intuitively I'd say that it's a bit weird to upsert an a into a (Map k b).

So far I don't really see a convincing case for extending the API. For now I'd suggest to use alter (and possibly optimize it and enhance its documentation).

[Vlix]

Yeah, me neither, but I just wanted to further explain what this Issue was started with: me erroneously assuming insertWith could get a less restrictive type signature. But then realizing why that doesn't work, and realizing what I was looking for at that moment almost 2 years back. 👍

So this issue can be closed if it isn't for anything else.