@hackage / creditmonad

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.