fastsum: A fast open-union type suitable for 100+ contained alternatives

[ bsd3, data, library ] [ Propose Tags ]

This package provides Data.Sum, an open-union type, similar to the Union type that powers the implementation of Oleg Kiselyov's extensible-effects library.

Unlike most open-union implementations, this type is very fast to compile, even when the type-level list of alternatives contains hundreds of entries. Membership queries are constant-time, compiling to a single type-level natural lookup in a closed type family, unlike the traditional encoding of Union, which relies on recursive typeclass lookups. As such, this type lends itself to representing abstract syntax trees or other rich data structures.

This project is safe to use in production. Any performance problems at compile-time or runtime should be filed as bugs.


[Skip to Readme]

Modules

[Index] [Quick Jump]

Flags

Automatic Flags
NameDescriptionDefault
build-examplesDisabled

Use -f <flag> to enable a flag, or -f -<flag> to disable that flag. More info

Downloads

Note: This package has metadata revisions in the cabal description newer than included in the tarball. To unpack the package including the revisions, use 'cabal get'.

Maintainer's Corner

Package maintainers

For package maintainers and hackage trustees

Candidates

Versions [RSS] 0.1.0.0, 0.1.1.0, 0.1.1.1, 0.2.0.0
Change log ChangeLog.md
Dependencies base (>=4.7 && <5), deepseq (>=1.4 && <2), fastsum, ghc-prim (>=0.5 && <1), hashable (>=1.2 && <2), template-haskell (>=2.12 && <2.17) [details]
License BSD-3-Clause
Copyright Rob Rix, Josh Vera, Allele Dev, Patrick Thomson 2016-2018
Author Rob Rix, Josh Vera, Allele Dev, Patrick Thomson
Maintainer patrickt@github.com
Revised Revision 1 made by patrick_thomson at 2020-10-18T21:37:50Z
Category Data
Home page https://github.com/patrickt/fastsum#readme
Source repo head: git clone https://github.com/patrickt/fastsum
Uploaded by patrick_thomson at 2019-12-11T17:59:57Z
Distributions
Reverse Dependencies 2 direct, 0 indirect [details]
Executables examples
Downloads 3360 total (13 in the last 30 days)
Rating (no votes yet) [estimated by Bayesian average]
Your Rating
  • λ
  • λ
  • λ
Status Docs available [build log]
Last success reported on 2019-12-11 [all 1 reports]

Readme for fastsum-0.1.1.1

[back to package description]

fastsum

This package provides Data.Sum, an open-union type, similar to the Union type that powers the implementation of Oleg Kiselyov's extensible-effects library.

Unlike most open-union implementations, this type is very fast to compile, even when the type-level list of alternatives contains hundreds of entries. Membership queries are constant-time, compiling to a single type-level natural lookup in a closed type family, unlike the traditional encoding of Union, which relies on recursive typeclass lookups. As such, this type lends itself to representing abstract syntax trees or other rich data structures.

GHC 8's support for custom type errors provides readable type errors should membership constraints not be satisfied.

In order to achieve speed, this package makes fewer guarantees about what can be proven given a Member instance. If you require a richer vocabulary to describe the implications of membership, you should use the traditional implementation of open-unions.

Credits

This library is built on the work of Oleg Kiselyov, which was then modified by Allele Dev. It was extracted from Josh Vera's effects library. Rob Rix implemented the ElemIndex type family and the Apply typeclass.