tweag / tweag/linear-base

Unlifted standard classes

Open
#418 2 comments 0 reactions 0 assignees View on GitHub

Nobody has claimed this yet.

Dominant language
Haskell
Stars
359
Forks
45
PR merge metrics
No merged PRs in 30d

Description

Is your feature request related to a problem? Please describe.

GHC is shipped with UnliftedDatatypes extension, but base library has similar issue like with LinearTypes extension i.e. doesn't support it well. Even basic standard classes (Show/Eq/Ord/Num) are not supported. Unlifted and Linear types are both extensions are driven by performance ghost.

There is no much action around making better support of Unlifted types.
I spot 1 semi stale discussion https://github.com/ghc-proposals/ghc-proposals/pull/30 and conclusion to reimplement a library of standard classes with levity polymorphic support in 3rd party library.

https://github.com/ekmett/unboxed

I looked at linear-base it just reexports Show from Prelude.

I curious why Unlifted extension is not used in linear-base - the library already has different class hierarchy - so (e.g. how Num is defined)

Performance gain from Unlifted extension is noticable, but combining code with different levity without common classes is hard:

benchmarking Fold Lifted/Left
time                 218.2 μs   (216.1 μs .. 220.4 μs)
                     0.999 R²   (0.999 R² .. 1.000 R²)
mean                 222.1 μs   (220.4 μs .. 224.3 μs)
std dev              6.753 μs   (4.599 μs .. 11.13 μs)
variance introduced by outliers: 26% (moderately inflated)

benchmarking Fold Unlifted/Left
time                 11.63 μs   (11.50 μs .. 11.80 μs)
                     0.998 R²   (0.997 R² .. 0.999 R²)
mean                 11.82 μs   (11.67 μs .. 12.06 μs)
std dev              689.3 ns   (459.1 ns .. 1.024 μs)
variance introduced by outliers: 67% (severely inflated)

https://github.com/yaitskov/lifted-vs-unlifted-benchmark/tree/6354d13bf4e36fd1aa93ec70bf19c2b8cb583608

Contributor guide

Open the contributing guide

First steps

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. Open a pull request that references the issue number.

Research direction

Start by reading the linked GHC proposal discussion, the linear-base Prelude re-export of Show, and the referenced unboxed library to understand existing approaches to levity-polymorphic classes. Compare those approaches with the benchmark context and establish a concrete scope, affected standard classes, and acceptance criteria before implementation.

Written by the indexing model from the issue text.

Assessment

Tech stack
haskell
Domain
compilers
Issue type
Feature
Difficulty
5/5
Estimated time
Over a week
Activity status
Stale
Clarity
Needs clarification
Newbie friendliness
20/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.