haskell / haskell/containers

Improved representation for Set and Map

Open
#1,073 3 comments 0 reactions 0 assignees View on GitHub
discussion/rfc Map performance Set
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

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.