creditmonad: Reasoning about amortized time complexity
This is a package candidate release! Here you can preview how this package release will appear once published to the main package index (which can be accomplished via the 'maintain' link below). Please note that once a package has been published to the main package index it cannot be undone! Please consult the package uploading documentation for more information.
Warnings:
- [option-o2] 'ghc-options: -O2' is rarely needed. Check that it is giving a real benefit and not just imposing longer compile times on your users.
Persistent data structures are ubiquitous in functional programming languages and their designers frequently have to reason about amortized time complexity. But proving amortized bounds is difficult in a persistent setting, and pen-and-paper proofs give little assurance of correctness, while a full mechanization in a proof assistant can be too involved for the casual user. This package defines a domain specific language for testing the amortized time complexity of persistent data structures using QuickCheck. The DSL can give strong evidence of correctness, while imposing low overhead on the user. The package includes implementations and tests of all lazy data structures given in Okasaki's book. See the paper "Lightweight Testing of Persistent Amortized Time Complexity in the Credit Monad" (2025) for a detailed description.
Properties
| Versions | 1.0.0, 1.0.0 |
|---|---|
| Change log | CHANGELOG.md |
| Dependencies | base (>=4.13 && <5), containers (>=0.6 && <1.7), creditmonad, mtl (>=2.3 && <2.4), prettyprinter (>=1.7 && <1.8), QuickCheck (>=2.14 && <3), STMonadTrans (>=0.4 && <0.5), unliftio (>=0.2 && <0.3) [details] |
| License | BSD-3-Clause |
| Author | Anton Lorenzen <anton.lorenzen@ed.ac.uk> |
| Maintainer | Anton Lorenzen <anton.lorenzen@ed.ac.uk> |
| Category | Development |
| Home page | https://github.com/anfelor/creditmonad#readme |
| Bug tracker | https://github.com/anfelor/creditmonad/issues |
| Source repo | head: git clone https://github.com/anfelor/creditmonad |
| Uploaded | by anfelor at 2025-07-20T12:33:04Z |
Modules
[Index] [Quick Jump]
- Control
- Monad
- Test
- Test.Credit
- Deque
- Test.Credit.Finger
- Heap
- Queue
- RandomAccess
- Sortable
- Test.Credit
Downloads
- creditmonad-1.0.0.tar.gz [browse] (Cabal source package)
- Package description (as included in the package)
Maintainer's Corner
Package maintainers
For package maintainers and hackage trustees