Categorical Models of Amortized Cost: An Adjoint Relationship between Cost and Potential

David Binder, David Corfield, Dominic Orchard +1

Various type systems have been developed to track the cost $\kappa$ of a computation using a cost-tracking monad $M\kappa \tau$. On its own, this only tracks the worst-case cost of a computati…