haskell
Too restrictive type signatures
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)
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.
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
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
Is there anything that ought to be addressed in this issue? Currently I'm a bit confused.
@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, I think this is really just another instance of people complaining about how wretched the
insertWithtype 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 (https://github.com/haskell/containers/issues/333, https://github.com/haskell-unordered-containers/unordered-containers/issues/264) is more grave IMHO since the behaviour is so counterintuitive. That it internally uses insertWith seems like an implementation detail to me though.
Personally, I have to look up the insertWith documentation every single time I want to use it.
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.
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.
Should we perform manual worker/wrapper with unboxed sums to try to improve
alterperformance? 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 https://github.com/haskell/containers/pull/523 related?!)
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.
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
@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).
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. :+1:
So this issue can be closed if it isn't for anything else.