Take a look at the alterF implementations

[meooow25]

Check if we can improve/simplify some things.

For instance, I don't really like that Set's alterF always allocates the changed set (previously mentioned in #1169 (comment)). I would like to try changing it to the bitqueue approach from Map's alterF.

[meooow25]

I decided to benchmark all the Set alterF implementations I can think of: https://gist.github.com/meooow25/e919ae830fb429bab817e57d5f953e7d

To briefly describe them, they are

1. The current implementation ("current")
2. member, then insert or delete ("twopass")
3. Just like alter but with fmap at each step ("simple")
4. Trace the path, and use it to modify the tree if needed ("bitqueue", "index")
5. Go down to the target while keeping track of how to reconstruct the tree ("cont", "stackstrict", "stacklazy")

Unsurprisingly, the current implementation performs poorly when the set does not need to be modified.

I think the Map alterF strategy (4) is a good selection of tradeoffs. It may traverse the tree twice, but it minimizes everything else: the number of comparisons, the number of allocations, and the number of fmaps. Interestingly, in this strategy "index" seems to be a little faster than "bitqueue" while also being simpler to implement. I plan to replace the Set implementation with this, if I don't find anything better.

[meooow25]

While looking around I spotted that Data.Map.alterF is too strict.

> import Data.IntMap as IntMap
> import Data.IntSet as IntSet
> import Data.Map as Map
> import Data.Set as Set
> import Data.Proxy
> IntMap.alterF (\_ -> Proxy) undefined undefined `seq` ()
()
> IntSet.alterF (\_ -> Proxy) undefined undefined `seq` ()
()
> Set.alterF (\_ -> Proxy) undefined undefined `seq` ()
()
> Map.alterF (\_ -> Proxy) undefined undefined `seq` ()
*** Exception: Prelude.undefined

[meooow25]

I think this is good enough for now.

I am wondering whether we should also change Map to use an index instead of bitqueue. Judging by the Set benchmarks the performance will be comparable, so the only benefit will be simplifying the implementation and deleting a bunch of code. I will open a new issue if I try it later.