haskell / haskell/containers

Lower Seq by a level

Open
#406 5 comments 0 reactions 0 assignees View on GitHub
performance Seq
Dominant language
Haskell
Stars
355
Forks
194
Avg merge
3d 4h
Merged PRs (30d)
4

Description

It has occurred to me that a `Node (Elem a)` is wasting quite a bit of space, since it stores an `Int` as well as the three pointers to `newtype`s. The `newtype` noise is often distracting as well. It seems to me it would be simpler to have `Elem` be like a first-level `Node`:

```haskell
data Elem a
= Elem2 a a
| Elem3 a a a

instance Sized (Elem a) where
size (Elem2 {}) = 2
size (Elem3 {}) = 3
```

Have a similar definition for top-level `Digit`s:

```haskell
data DigitS a
= OneS a
| TwoS a a
| ThreeS a a a
| FourS a a a a

instance Sized (DigitS a) where
size (OneS {}) = 1
size (TwoS {}) = 2
size (ThreeS {}) = 3
size (FourS {}) = 4
```

And then, at the top level, `Seq` is no longer a `newtype`:

```haskell
data Seq a
= EmptyS
| SingleS a
| DeepS {-# UNPACK #-} !Int !(DigitS a) !(FingerTree (Elem a)) !(DigitS a)
```

You can probably use regular `Digit`s instead of `DigitS`s if you remember to use a specific top-level `digitSize` function instead of just regular `size`.

This means that getting the sizes of `Node`s no longer involves adding a bunch of 1s together; it means that functions operating on `Seq`s (for instance, `(|>)`) can be inlined; you don't need to worry about `coerce` not working on older versions of GHC; and several other benefits.

The question, then, is if it's worth the increase in code size and complexity.

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.