haskell / haskell/containers

Cleanup after IntMap rewrite

Open
#698 49 comments 2 reactions 0 assignees View on GitHub
IntMap
Dominant language
Haskell
Stars
355
Forks
194
Avg merge
3d 4h
Merged PRs (30d)
4

Description

This ticket summarizes things that should be done either before or soon after the enormous `IntMap` replacement in #340.

### Before merge

- [x] Reinstate the export list in `Data.IntMap.Internal`.

- [x] Add an export list to `Data.IntMap.Merge.Internal`.

- [ ] Diff Haddocks to make sure no functions or instances have gone missing.

- [ ] Generate a final benchmark comparison. I prefer to see these interleaved or side by side rather than one whole set after another, but I won't insist on it. This should go in the commit message for the final squashed commit.

- [ ] Try a bit harder to optimize `union`.

- [x] See what non-merge functions can be defined in terms of merge tactics and `runMissingAll`. (More would require a restructuring of the module boundaries.)

- [x] Improve test coverage, especially of merge tactics and `isSubmapOf`. (Side question: should we bump up the number of test cases Travis asks for?)

- [x] Add internal documentation for merges and deletion.

- [x] Reinstate rewrite rules and the phased `INLINE` and `NOINLINE` directives needed to make them work. Many of them (e.g., map fusion rules and map/coerce) are unconditional improvements. Others (relating to list conversions) are *likely* desirable.

- [ ] Check that GHC can use the new IntMap without (undue) performance degradation. (@sjakobi has offered to trigger the build jobs for this.)

- [x] See if anything can be done about the object code duplication resulting from the alternating levels. Is there some clever way to make them uniform enough to share code? (Sadly, the answer appears to be no, for reasons that are not entirely obvious. Flipping over to the `complement` of the key each time we go left seems to hurt lookups significantly, although not enormously.)

### After merge

- [ ] See if anything can be done about the source code duplication resulting from the alternating levels. Is there some clever way to make them uniform enough to share code?

- [ ] Rewrite `IntSet` to match. Hopefully this is fairly mechanical, replacing values by bitmaps. Once this is done, get rid of bit twiddling utilities that are no longer used.

- [ ] Pick up #653 and see how well it works with the new representation.

- [ ] Optimize `merge`.

- [ ] Resolve the strictness guarantees of `fromAscList` and friends. See #473 and https://github.com/haskell/containers/pull/340#issuecomment-247811863.

- [ ] Consider using more type wrappers for safety.

- [ ] Evaluate using unboxed sums for intermediates. These are not always a win, but sometimes are.

- [ ] Expand the benchmarks to cover more functions. Check for major regressions that the current benchmarks missed.

- [ ] Consider adding as permanent APIs things that came up in the implementation:
- `runMissingAll :: WhenMissing f a b -> IntMap a -> f (IntMap b)`, plus maybe a pure variant. (DF: I'm not so convinced yet. What's it for?)
- `traverseMaybeWithKey :: (Key -> a -> f (Maybe b)) -> IntMap a -> f (IntMap b)` (DF: yes, we most definitely want this by some name or other.)
- `dropMatched :: WhenMatched f a b c`
- `firstMatched :: WhenMatched f a b a` (and `secondMatched :: WhenMatched f a b b`)
- `fold` variants that can ignore or be otherwise loose with ordering. (see https://github.com/haskell/containers/issues/698#issuecomment-569558952, but more generally)

### Uncategorized

- [ ] Check whether the restructuring in #658 is a good idea for the new representation and, if so, reinstate it.

- [ ] Continue to add internal documentation. For example, `isSubmapOf` and the like are pretty confusing.

- [ ] Shorten long lines when reasonable. We generally aim for 80 characters or fewer. There's flexibility for unusual situations, but this code has some very long lines that could be broken cleanly.

- [x] Use `liftA*` in `mergeA`.

- [ ] Evaluate whether we can get the same performance using `foldMapDefault`, `fmapDefault`, and equivalent tricks for keyed versions. That would cut down on source code.

- [ ] Evaluate whether we should implement `alter` "by hand" as we used to. If not, then we should probably implement it using `alterF @Identity`.

Contributor guide

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.