New convenience function for Data.Map

[nmichael44]

Consider inserting (k, v) elements into a map (Data.Map) in a
scenario where if the element exists you want to combine the new
element (v) with the old existing element. For this we have function:

insertWith :: Ord k => (a -> a -> a) -> k -> a -> Map k a -> Map k a

which does the trick.

But consider this scenario:

m : Map Key [Values]

and when we insert we want to add another value to the list if the key
is there.

We now have to do:

insertWith (++) k [newV] m

So we need to build a new singleton list and then call append from
every insert. The suggestion is to add a new function in which we
parametrize more generally over the value of the map as below.

insertWith' :: Ord k => (a -> m a -> m a) -> (a -> m a) -> k -> a
                        -> M.Map k (m a) -> M.Map k (m a)

The behavior we want is the following but without the double tree
traversal (2*log(n)) cost.

insertWith' f g k a m
  = M.insert
             k
             (case M.lookup k m of
                Nothing -> g a
                Just ma -> f a ma)
             m

With such a function for the example above we could then do:

insertWith' (:) (: []) k a m

and so avoid creating the singleton lists. Of course this is not specific to lists... it would help with any container value in the position of map value.

[sjakobi]

I'm not convinced by the motivation yet. If you compare

insertWith (++) k [a] m

and

insertWith' (:) (: []) k a m

the insertWith version is shorter and also has one argument less, so it seems easier to understand.

[Lysxia]

If the concern is to avoid creating a singleton only to append it immediately, there is alter.

[nmichael44]

My motivation was first performance (less allocation) and second convenience. Yes, insertWith has one less argument and is easier to understand but the scenario I describe has an impedance mismatch with that function. It doesn't do what I need exactly -- I have to box the value just to unbox it the very next instance -- it fells wrong. I am relatively new to Haskell and I needed the functionality I describe a few times. And the first few times I was so surprised that I couldn't find it, that I went over the list of functions in Data.List just in case I missed something. This version is clearly more general and subsumes the existing one -- I see no reason it shouldn't be there.

I am not suggesting getting rid of anything -- just adding this variant of the function.

By alter I assume you mean this function:

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

But here I don't get to supply a value so I have to capture my newV inside a closure and thus allocate again which is what I was trying to avoid.

[konsumlamm]

Using alter you can write your function like this:

insertCons :: (Ord k) => k -> a -> Map k [a] -> Map k [a]
insertCons k v = alter f k
  where
    f Nothing = Just [v]
    f (Just vs) = Just (v : vs)

This avoids traversing the map twice, but still does some boxing (though I wouldn't be surprised if that gets optimized away). I'm not exactly sure why capturing a value would necessarily allocate though. (Not trying to be condescending, but if you want to have as few allocations as possible, I'm not sure Haskell is the right language for you anyway.)

The function you're proposing is too specialized IMO (btw, I think it would make more sense to propose using b instead of m a, if this is actually implemented) and I think there are already enough related functions that could be used instead (even though they may be slightly less performant). If you want to write this the most performant way, you could use the Data.Map.Internal module to implement this function yourself, but since you said you were new to Haskell, I wouldn't recommend doing that.

Considering the scenario, what you're actually doing seems to be simulating a multimap. For that, using Set a instead of [a] as the value type would probably be faster. I'd also recommend looking at a specialized multimap implementation, like more-containers or multi-containers. These also use a Map under the hood, but they provide a specialized multimap API.

[nmichael44]

I covered your first point in my previous message (building a closure will allocate unless by magic everything gets inlined the right way -- which is no way to live :).

As to your second point and your suggestion of using b instead of m a, I think you are not correct. Try writing the function as you suggest and you will soon see that it doesn't type check. In a pure function f :: a -> b -> b (with no exceptions, bottom etc) you can't receive an a and a b, then produce a b having done something meaningful with a. You can't use a in any meaningful way. m a feels like the right generalization.

In fact function f :: a -> b -> b is the function (swap const) but I could be wrong -- as I said I am new to the language.

As to the Haskell-is-not-the-language-for-you-if-you-don't-want-to-allocate-too-much argument I don't buy it. True, Haskell allocates a lot, but a programming language is a tool to build all kinds of programs -- for some allocation is no big deal but for others it is. I don't see why I have to compromise. What I have proposed is an improvement both in terms of allocation and (I believe) in terms of API.

As to the last suggestion of using Set instead of [a], this could work when what you were collecting was a Set but if it's not (and you want the duplicates) then no cigar. What I proposed would work nicely when you are collecting a Set by the way, or a List or a Vector, or a Seq, or an Either e or a Maybe, etc etc -- it is in fact much more general than what we have.

[konsumlamm]

As to your second point and your suggestion of using b instead of m a, I think you are not correct. Try writing the function as you suggest and you will soon see that it doesn't type check. In a pure function f :: a -> b -> b (with no exceptions, bottom etc) you can't receive an a and a b, then produce a b having done something meaningful with a. You can't use a in any meaningful way. m a feels like the right generalization.

That's only true when you want to write a function that's generic over a and b, but when using the function, b can be whatever you want, including [a]. You could implement it like this (even without alter):

insertWith' :: (Ord k) => (a -> b -> b) -> (a -> b) -> k -> a -> Map k b -> Map k b
insertWith' f g key x = insertWith (const (f x)) key (g x)

insertCons :: (Ord k) => k -> a -> Map k [a] -> Map k [a]
insertCons key value = insertWith' (:) pure key value

What I proposed would work nicely when you are collecting a Set by the way, or a List or a Vector, or a Seq, or an Either e or a Maybe, etc etc -- it is in fact much more general than what we have.

As you can see, it can be implemented using insertWith (or alter), so it's not really more general.

[nmichael44]

Thank you for that insight. I rewrote it slightly to understand what you did:

insertWith' f g key x = M.insertWith (\vnew vold -> f x vold) key (g x)

and the point is you never use vnew so the types work out. Great! I had also tried this at first but I was doing f vnew vold which does not typecheck.

As for the generality issue, I think you have misunderstood what I meant probably because I didn't explain it well. It is more general in the sense that it can do what the existing functions can do without allocating anything. With your (admittedly more general) API above (mapping to b instead of m a), the implementation creates 2 closures (one for the lambda and another for (g x) (so it's worse than what we started with which was just 1 boxed value insertWith (++) k [a] m) while the API that I proposed allocates nothing.

I looked at the implementation and it looks easy to implement my version. If you decide to add it let me know and I can send a patch.

[nmichael44]

It appears to me (please correct me if I am wrong) that there is another performance issue with your implementation here:

insertWith' :: (Ord k) => (a -> b -> b) -> (a -> b) -> k -> a -> Map k b -> Map k b
insertWith' f g key x = insertWith (const (f x)) key (g x)

If the key is already in the map we end up calling both f and g (for strict maps) -- but we only really needed to call f in that case. So not only do we have to build 2 closures (as described in the previous message), we also have to pay for execution of g and whatever boxed objects it produces (which are never used).

[nmichael44]

I have implemented the above proposal with an alternative interface as suggested by @konsumlamm . I have tentatively named the function insertWithFun (betters names are welcome). The new interface now looks like:

insertWithFun :: Ord k => (a -> b -> b) -> (a -> b) -> k -> a -> Map k b -> Map k b

The pull request is here: #785

If you decide you like the new function, please review carefully!

[treeowl]

I'm not really a fan of these closure-avoidance functions. I'd much rather see if we can get good performance from friendlier APIs.

…

On Sun, Jun 27, 2021, 6:05 PM Neo ***@***.***> wrote: I have implemented the above proposal with an alternative interface as suggested by @konsumlamm <https://github.com/konsumlamm> . I have tentatively named the function insertWithFun (betters names are welcome). The new interface now looks like: insertWithFun :: Ord k => (a -> b -> b) -> (a -> b) -> k -> a -> Map k b -> Map k b The pull request is here: #785 <#785> If you decide you like the new function, please review carefully! — You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub <#784 (comment)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/AAOOF7KWHDPFJ7WPPBHTOVTTU6OBXANCNFSM47LP63AA> .

[nmichael44]

@treeowl But how? It's not really possible with the existing apis (alter, insertWith). Boxes and closures are your only choice. And the case I am describing happens often enough in real code -- building a Map from some Key to a Set or a List, or a Vector, or another Map etc. I have not been using Haskell long but it happened to me often enough to annoy me enough to propose this addition. And honestly I wouldn't call the API of this function unfriendly -- it's just one more argument than the existing functions.

It's of course up to you guys if you want to include it but I hope you do.

[treeowl]

What I have wanted for ages is something more like insyboggle :: Ord k => v -> (v -> v) -> k -> Map k v -> Map k v which is equivalent to gadzooks :: Ord k => (Maybe v -> v) -> k -> Map k v -> Map k v The only problem is the pesky closure creation. Is there a way to manipulate arity and inlining to make that problem go away?

…

On Sun, Jun 27, 2021, 6:24 PM Neo ***@***.***> wrote: @treeowl <https://github.com/treeowl> But how? It's not really possible with the existing apis (alter, insertWith). Boxes and closures are your only choice. And the case I am describing happens often enough in real code -- building a Map from some Key to a Set or a List, or a Vector, or another Map etc. I have not been using Haskell long but it happened to me often enough to annoy me enough to propose this addition. And honestly I wouldn't call the API of this function unfriendly -- it's just one more argument than the existing functions. It's of course up to you guys if you want to include it but I hope you do. — You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub <#784 (comment)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/AAOOF7IGLKJSZIHVSF77XHLTU6QKNANCNFSM47LP63AA> .