haskell / haskell/containers

Can we de-duplicate Set/Map by leveraging common structure?

Open
#851 10 comments 1 reaction 0 assignees View on GitHub
code-quality discussion/rfc
Dominant language
Haskell
Stars
355
Forks
194
Avg merge
3d 4h
Merged PRs (30d)
4

Description

Looking at https://github.com/haskell/containers/pull/817 's
```haskell
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
```haskell
newtype Map k a = Map (Set (Arg k a))
```
since
```haskell
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
```haskell
newtype Set a = Set (BinTree a)
newtype Map k v = Map (BinTree (Arg k v))
```
allowing a good deal of functions to simply delegate
```haskell
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.

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.