Improved representation for Set and Map
Nobody has claimed this yet.
Assessment
- Difficulty
- 5/5
- Estimated time
- Over a week
- Newbie friendliness
- 20/100
- Issue type
- Refactor
- Clarity
- Needs clarification
- Activity status
- Stale
- Tech stack
- haskell
- Domain
- performance
Research direction
Review the current Set and Map representations and the referenced containers PR #1069 discussion first; the issue does not identify implementation files or tests. Determine which proposed representation is selected, then validate the invariants and the claimed memory and performance effects before considering the work complete.
Written by the indexing model from the issue text.
Description
Consider changing the representation to avoid Tips.
Suggested by wrengr in https://github.com/haskell/containers/pull/1069#issuecomment-2504945201
I'm thinking
data Set a
= Bin !Int !a !(Set a) !(Set a)
| Two !a !a
| One !a
| Nil -- Invariant: Never a child of Bin
This hopefully improves performance but certainly improves memory usage. Compared to today, for n elements we can avoid storing ~n Tips and ~n/2-2n/3 Ints.
Alternately, as midway between current and the above,
data Set a
= Bin !Int !a !(Set a) !(Set a)
| One !a
| Tip
-- Invariant: Bin _ x Tip Tip is always replaced with One x
This puts the match-on-singleton idea of #1069 into the type. Avoids storing ~2n/3-n Tips and ~n/3-n/2 Ints.
- Dominant language
- Haskell
- Stars
- 355
- Forks
- 194
- Avg merge
- 2d 12h
- Merged PRs (30d)
- 6
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 ·
-
Difficulty 5/5 Over a week Newbie friendliness 35/100
haskell/containers#1261 · 9 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 ·
-
Difficulty 4/5 3-5 days Newbie friendliness 50/100
haskell/containers#1242 ·
All issues in haskell/containers
Similar issues
-
bug good-title pdd
Difficulty 2/5 Under an hour Newbie friendliness 82/100
objectionary/phino#1630 ·
Maintainers usually reply within 1 day