nonempty IntSet?
Open
discussion/rfc
IntSet
performance
- Dominant language
- Haskell
- Stars
- 355
- Forks
- 194
- Avg merge
- 3d 4h
- Merged PRs (30d)
- 4
Description
When reading #616 I tought about IntSet. Currently,
```
data IntSet = Bin {-# UNPACK #-} !Prefix {-# UNPACK #-} !Mask !IntSet !IntSet
-- Invariant: Nil is never found as a child of Bin.
| Tip {-# UNPACK #-} !Prefix {-# UNPACK #-} !BitMap
| Nil
```
By making the invariant more explicit, this could be changed to something like
```
data IntSetNE = Bin .. | Tip ..
data IntSet = Maybe IntSetNE
```
with `IntSetNE` exported - or not, but my point is, this reduces the number of constructors of the tree (from 3 to 2), and this might give shorter code (source and machine), maybe faster code, and less memory.
Contributor guide
Assessment
This issue has not been assessed yet.