haskell / haskell/containers

nonempty IntSet?

Open
#669 2 comments 0 reactions 0 assignees View on GitHub
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

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.