creditmonad: Reasoning about amortized time complexity

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.

Modules

[Index] [Quick Jump]

Downloads

• creditmonad-1.0.0.tar.gz [browse] (Cabal source package)
• Package description (as included in the package)

Maintainer's Corner

Package maintainers

• anfelor

For package maintainers and hackage trustees

• edit package information

Candidates

• 1.0.0