  Amortized analysis is a cost analysis technique for data structures in which
cost is studied in aggregate, rather than considering the maximum cost of a
single operation. Traditionally, amortized analysis has been phrased
inductively, in terms of finite sequences of operations. Connecting to prior
work on coalgebraic semantics for data structures, we develop the perspective
that amortized analysis is naturally viewed coalgebraically in the category of
algebras for a cost monad, where a morphism of coalgebras serves as a
first-class generalization of potential function suitable for integrating cost
and behavior. Using this simple definition, we consider amortization of other
sample effects, non-commutative printing and randomization. To support
imprecise amortized upper bounds, we adapt our discussion to the bicategorical
setting, where a potential function is a colax morphism of coalgebras. We
support parallel data structure usage patterns by using coalgebras for an
endoprofunctor instead of an endofunctor, combining potential using a monoidal
structure on the underlying category. Finally, we compose amortization
arguments in the indexed category of coalgebras to implement one amortized data
structure in terms of others.
