Full IntSets?
Nobody has claimed this yet.
Assessment
- Difficulty
- 5/5
- Estimated time
- Over a week
- Newbie friendliness
- 25/100
Research direction
The issue names no files, tests, or entry points. Start by reviewing the existing IntSet representation and considering the proposed Full Prefix constructor against contiguous-run use cases such as GHC. Done would require a tested design and real-world measurements showing whether memory savings outweigh the added overhead.
Written by the indexing model from the issue text.
Description
I wonder if it will be useful to add another constructor to IntSet: Full Prefix. This indicates that this is a full tree with a shared prefix.
I expect this to show good improvements for use cases where contiguous runs of Ints are likely. It will also reduce space usage in such cases. For instance, to store [0..n] we will need only $O(\log n)$ memory instead of $O(n)$.
But this would add small overheads in various places, so it will likely not be a clear win in all use cases.
Also, to be clear, this would be small added costs and not a change in the worst case bounds.
For sure we would want to test something like this out on some real world use cases (like GHC, maybe others?) to see how it affects things. Just documenting this idea for now.
- Dominant language
- Haskell
- Stars
- 356
- Forks
- 194
- Avg merge
- 3d 42m
- Merged PRs (30d)
- 5
Getting set up
- No Dockerfile or Docker Compose file
- No pull request template
- Read the contributing guide
First steps
- Read the whole issue, then the project's contributing guide.
- Comment on the issue to say you are picking it up — it saves two people doing the same work.
- Fork the repository and make your change on a branch.
- Open a pull request that references the issue number.
More from haskell/containers
-
major-release strictness Tree
Difficulty 2/5 1-3 hours Newbie friendliness 72/100
haskell/containers#1260 ·
-
low-hanging-fruit performance Seq
Difficulty 4/5 3-5 days Newbie friendliness 43/100
haskell/containers#1262 · 2 comments ·
-
Difficulty 5/5 Over a week Newbie friendliness 35/100
haskell/containers#1261 · 11 comments ·
-
IntSet low-hanging-fruit performance
Difficulty 3/5 1-2 days Newbie friendliness 58/100
haskell/containers#1251 ·
-
maintainability major-release
Difficulty 3/5 1-2 days Newbie friendliness 70/100
haskell/containers#1250 ·
All issues in haskell/containers
Similar issues
-
status: needs triage type: enhancement
Difficulty 1/5 Under an hour Newbie friendliness 90/100
haskell/haskell-language-server#5128 ·
Maintainers usually reply within 1 day
-
enhancement
Difficulty 2/5 1-3 hours Newbie friendliness 62/100
alunduil/siren-json.hs#246 ·
Maintainers usually reply within 1 day
-
frontend Hackathon
Difficulty 2/5 1-3 hours Newbie friendliness 72/100
flora-pm/flora-server#1334 · 1 comment ·
Maintainers usually reply within 1 day
-
question
Difficulty 1/5 Under an hour Newbie friendliness 75/100
NixOS/SC-election-2026#44 · 1 reaction ·
Maintainers usually reply within 1 day
-
enhancement good first issue hacktoberfest runner
Difficulty 2/5 1-3 hours Newbie friendliness 82/100