Can we de-duplicate Set/Map by leveraging common structure?
Nobody has claimed this yet.
Assessment
- Difficulty
- 5/5
- Estimated time
- Over a week
- Newbie friendliness
- 25/100
Research direction
Start with src/Data/Map/Internal.hs and the related Set and Map.Lazy implementations, then compare the shared operations described in pull request 817, including null, size, member, and insert. Investigate whether a shared BinTree representation preserves the stated roles, laziness, and performance. Done means a validated design direction with its trade-offs and an agreed scope for deduplication.
Written by the indexing model from the issue text.
Description
Looking at https://github.com/haskell/containers/pull/817 's
argSet :: Map k a -> Set.Set (Arg k a)
argSet Tip = Set.Tip
argSet (Bin sz kx x l r) = Set.Bin sz (Arg kx x) (argSet l) (argSet r)
it seems the two structures are the same "up to parenthesization"
I wonder if one could exploit this to de-duplicate a good deal of code.
It's not as simple as
newtype Map k a = Map (Set (Arg k a))
since
type role Map nominal representational
type role Set nominal
causes
src/Data/Map/Internal.hs:465:1-38: error:
• Role mismatch on variable a:
Annotation says representational but role nominal is required
• while checking a role annotation for ‘Map’
|
465 | type role Map nominal representational
| ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
but maybe we could have the binary tree structure be its own type and then
newtype Set a = Set (BinTree a)
newtype Map k v = Map (BinTree (Arg k v))
allowing a good deal of functions to simply delegate
null :: Set a -> Bool
null (Set t) = BinTree.null t
null :: Map k a -> Bool
null (Map t) = BinTree.null t
There are obvious examples like null, size, member but Set and Map.Lazy may have more similarities - insert seems pretty much the same "up to parenthesization".
It's not obvious to me whether Map can be decomposed like this, since the extra indirection (in this case data Arg a b) interferes with lazyness and performance.
- Dominant language
- Haskell
- Stars
- 356
- Forks
- 195
- Avg merge
- 2d 17h
- Merged PRs (30d)
- 2
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 ·
-
Map performance Set
Difficulty 5/5 Over a week Newbie friendliness 35/100
haskell/containers#1263 · 5 comments ·
-
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 ·
All issues in haskell/containers
Similar issues
-
Difficulty 2/5 1-3 hours Newbie friendliness 62/100
haskell-beam/beam#828 ·
-
Difficulty 2/5 1-3 hours Newbie friendliness 72/100
simplex-chat/simplex-chat#7755 ·
Maintainers usually reply within 1 day
-
bug core-libs
Difficulty 2/5 1-3 hours Newbie friendliness 68/100
-
content good first issue
Difficulty 2/5 Under an hour Newbie friendliness 88/100
StudentSuite/awesome-skills-plugins-for-students#312 ·
Maintainers usually reply within 1 day
-
Difficulty 1/5 Under an hour Newbie friendliness 96/100
alunduil/collection-json.hs#415 ·
Maintainers usually reply within 1 day