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: https://github.com/haskell/containers/pull/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 https://github.com/haskell/containers/pull/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 https://github.com/haskell/containers/issues/784#issuecomment-869229803, 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 https://github.com/haskell/containers/issues/784#issuecomment-869232074, or unsubscribe https://github.com/notifications/unsubscribe-auth/AAOOF7IGLKJSZIHVSF77XHLTU6QKNANCNFSM47LP63AA .

[nmichael44]

Let's have a closer look. Let for example v = Set w.

Calling insyboggle we must create a singleton set for its first argument (which it may not use) and a closure for the function (which it also may not use) so it can combine the old and new.

Calling gadzooks creates a closure to hold the new element so that it may use it to produce the singleton set or to combine it whatever is there.

I think there is no hope for insyboggle -- even if we get rid of the closure I don't think ghc is sophisticated enough to deconstruct a Set and avoid it's creation. For the second one, if it gets inlined in user code, and then if the (Maybe v -> v) function is also inlined there may be hope. In practice though this does not happen. Their implementation is typically large and recursive and ghc just gives up.

The function being proposed here does no allocation as the expense of one extra argument. I think it's small price to pay.

[Lysxia]

I think there is no hope for insyboggle -- even if we get rid of the closure I don't think ghc is sophisticated enough to deconstruct a Set and avoid it's creation.

That seems overly pessimistic about what GHC can optimize. In theory, simply inlining the singleton and the closure will avoid their creation. In fact I think this is doable by tweaking only alter. I could define your proposed insertWith' using alter and, with a small patch to alter and compiling with -fno-full-laziness, I could get the Core that one would want, without those extra allocations.

At the moment alter blocks inlining because f is a parameter to the recursive worker (the local function go). The changes to alter were:

1. Take f out from the parameters of go (for the reason described above)
2. Use INLINE instead of INLINEABLE for some reason I don't understand

Here's the modified function:

alter :: Ord k => (Maybe a -> Maybe a) -> k -> Map k a -> Map k a
alter f = go
  where
    -- go :: Ord k => (Maybe a -> Maybe a) -> k -> Map k a -> Map k a
    go !k Tip = case f Nothing of
               Nothing -> Tip
               Just x  -> singleton k x

    go k (Bin sx kx x l r) = case compare k kx of
               LT -> balance kx x (go k l) r
               GT -> balance kx x l (go k r)
               EQ -> case f (Just x) of
                       Just x' -> x' `seq` Bin sx kx x' l r
                       Nothing -> glue l r
-- #if __GLASGOW_HASKELL__
-- {-# INLINABLE alter #-}
-- #else
{-# INLINE alter #-}
-- #endif

Here's insertWith' using alter:

module CC (insertWith') where

import Data.Map (Map)
import qualified Data.Map.Strict as Map

insertWith' :: Ord k => (a -> b -> b) -> (a -> b) -> k -> a -> Map k b -> Map k b
insertWith' cons singleton k x = Map.alter (\oy -> Just $ case oy of
  Just y -> cons x y
  Nothing -> singleton x) k

Optimized Core (using cabal exec ghc -- -O -fno-full-laziness -dsuppress-all -ddump-simpl -ddump-to-file CC.hs); it's the body of alter, with the parameters of insertWith' inlined, i.e., no extra allocations for the closure and singleton:

insertWith'
  = \ @ k_a1y2
      @ a_a1y3
      @ b_a1y4
      $dOrd_a1y6
      cons_a1cW
      singleton_a1cX
      k1_a1cY
      x_a1cZ
      eta_B1 ->
      letrec {
        go7_s1zP
          = \ k2_a1yJ ds_a1yK ->
              case k2_a1yJ of k3_a1yL { __DEFAULT ->
              case ds_a1yK of {
                Bin ipv_a1yT ipv1_a1yU ipv2_a1yV ipv3_a1yW ipv4_a1yX ->
                  case compare $dOrd_a1y6 k3_a1yL ipv1_a1yU of {
                    LT ->
                      balance ipv1_a1yU ipv2_a1yV (go7_s1zP k3_a1yL ipv3_a1yW) ipv4_a1yX;
                    EQ ->
                      case cons_a1cW x_a1cZ ipv2_a1yV of x'1_a1za { __DEFAULT ->
                      Bin ipv_a1yT ipv1_a1yU x'1_a1za ipv3_a1yW ipv4_a1yX
                      };
                    GT ->
                      balance ipv1_a1yU ipv2_a1yV ipv3_a1yW (go7_s1zP k3_a1yL ipv4_a1yX)
                  };
                Tip ->
                  case singleton_a1cX x_a1cZ of x1_a1zg { __DEFAULT ->
                  Bin 1# k3_a1yL x1_a1zg Tip Tip
                  }
              }
              }; } in
      go7_s1zP k1_a1cY eta_B1

I did have to use -fno-full-laziness to avoid the extrusion of singleton x, but there may be a better way, and at least the other branch did not need any help. The problem is not that GHC is not sophisticated enough to do this optimization, on the contrary, the main obstacle is that it is applying an optimization too eagerly. So it might take some work to solve, but the situation with alter seems very far from hopeless.

[nmichael44]

@Lysxia I have tried your code (with ghc 8.10.4, options -O2 -fno-full-laziness) but I was not able to get ghc to inline alter. I didn't change INLINABLE to INLINE so that much be the reason. ghc may not inline an INLINABLE function for any number of reasons (some of them good) -- and those reasons change from version to version.

I am not sure what you are suggesting though. Are you suggesting to add the new function but instead implement it with alter (instead of directly as I did), and then find the right set on incantations when compiling containers to get ghc to get rid of the boxes/closures? Or are you saying that we don't need the new function altogether because we have alter and maybe we can get it to inline in user code? If it's the first, then I honestly don't see the point -- the implementation is so small it's not worth bothering with the refactoring. If it's the second, then first we have to find the right set of incantations to get ghc to inline and second we have to convince people to use those compiler options (be it no-full-laziness or whatever else) in their projects -- a losing game -- no one will do it (in fact specifying the options you want to get alter to inline may cause the user project to run slower -- after all full-laziness is the default for a reason).

[treeowl]

Whether you use an arity of one or two, you're sometimes going to change the arity of what the user passes/wants to pass. How do you decide which is more important?

On Mon, Jun 28, 2021, 9:37 AM Neo @.***> wrote:

I have tried your code (with ghc 8.10.4, options -O2 -fno-full-laziness) but I was not able to get ghc to inline alter. I didn't change INLINABLE to INLINE so that much be the reason. ghc may not inline an INLINABLE function for any number of reasons (some of them good) -- and those reasons change from version to version.

I am not sure what you are suggestiong though. Are you suggesting to add the new function but instead implement it with alter (instead of directly as I did), and then find the right set on incantations when compiling containers to get ghc to get rid of the boxes/closures? Or are you saying that we don't need the new function altogether because we have alter and maybe we can get it to inline in user code? If it's the first, then I honestly don't see the point -- the implementation is so small it's not worth bothering with the refactoring. If it's the second, then first we have to find the right set of incantations to get ghc to inline and second we have to convince people to use those compiler options (be it no-full-laziness or whatever else) in their projects -- a losing game -- no one will do it (in fact specifying the options you want to get alter to inline may cause the user project to run slower -- after all full-laziness is the default for a reason).

— You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub https://github.com/haskell/containers/issues/784#issuecomment-869692332, or unsubscribe https://github.com/notifications/unsubscribe-auth/AAOOF7KSXEXRPO2266URL2TTVB3JNANCNFSM47LP63AA .

[nmichael44]

@treeowl I am sorry but I don't understand your comment regarding 'arity' at all. Please elaborate.

[Lysxia]

I am indeed suggesting the latter option, that we somehow fix alter to inline right, and then users of the library can implement similar functions such as insertWith' on top of that.

I have tried your code (with ghc 8.10.4, options -O2 -fno-full-laziness) but I was not able to get ghc to inline alter.

The current definition of alter does not get inlined. That's why I added a patch to alter in my comment.

first we have to find the right set of incantations to get ghc to inline and second we have to convince people to use those compiler options

Or we implement alter so it optimizes well out-of-the-box so users don't need to do anything.

Maybe someone more knowledgeable about the internals of GHC can tell us

1. Whether to make alter INLINE or INLINEABLE, because INLINEABLE doesn't seem to enable inlining in the example above.
2. Whether it's possible to get an effect equivalent to -fno-full-laziness in a less invasive fashion.

[nmichael44]

@Lysxia ghc may decide not to inline a function for all sorts of reasons. The INLINE directive forces the inline but is that the right thing in all cases? alter is a fairly large function (which is probably why with INLINABLE ghc chooses not to inline it), and inlining it inside other large functions can cause explosion in the size of executable code trashing our code caches. My point is forcing it to always be inlined is not necessarily the right thing -- it will solve our closure problem but can cause others not immediately obvious. And there is the problem of the ghc switches that users would have to supply as I have outlined above so I won't repeat myself.

I believe the solution I have proposed is a reasonable compromise and it does make the Map interface better.

[sjakobi]

For now I'm more in favor of improving alter than adding yet another function to the API.

I'm wondering though how much performance we stand to gain from avoiding the overhead of closure allocation. All of the functions discussed end up allocating a new Map anyway. Does the cost of the closure still matter in comparison?

---

Regarding the functions that @treeowl suggests in https://github.com/haskell/containers/issues/784#issuecomment-869232625, see some previous discussion in https://github.com/haskell/containers/issues/538, particularly https://github.com/haskell/containers/issues/538#issuecomment-658892524.

[BurningWitness]

insyboggle :: Ord k => v -> (v -> v) -> k -> Map k v -> Map k v`

Calling insyboggle we must create a singleton set for its first argument (which it may not use) and a closure for the function (which it also may not use) so it can combine the old and new.

I fail to see the issue here since insyboggle a f k == insertWith (f k) k a and insertWith suffers from all the exact same evaluation issues (two potential outcomes with only one chosen deep inside the function).

---

The real question to me is why insertWith even duplicates a known argument in the first place, shouldn't this be called insertAssoc or something?