Improved representation for Set and Map
- Dominant language
- Haskell
- Stars
- 355
- Forks
- 194
- Avg merge
- 3d 4h
- Merged PRs (30d)
- 4
Description
Consider changing the representation to avoid `Tip`s.
Suggested by wrengr in https://github.com/haskell/containers/pull/1069#issuecomment-2504945201
---
I'm thinking
```hs
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 `Tip`s and ~n/2-2n/3 `Int`s.
Alternately, as midway between current and the above,
```hs
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 `Tip`s and ~n/3-n/2 `Int`s.
Contributor guide
Assessment
This issue has not been assessed yet.