Quotes from Chris Okasaki

The methodological benefits of functional languages are well known [Bac78, Hug89, HJ94], but still the vast majority of programs are written in imperative languages such as C. This apparent contradiction is easily explained by the fact that functional languages have historically been slower than their more traditional cousins, but this gap is narrowing.

A distinctive property of functional data structures is that they are always persistent—updating a functional data structure does not destroy the existing version, but rather creates a new version that coexists with the old one. Persistence is achieved by copying the affected nodes of a data structure and making all changes in the copy rather than in the original.

Amortization allows for occasional operations to have actual costs that exceed their amortized costs. Such operations are called expensive. Operations whose actual costs are less than their amortized costs are called cheap. Expensive operations decrease the accumulated savings and cheap operations increase it. The key to proving amortized bounds is to show that expensive operations occur only when the accumulated savings are sufficient to cover the remaining cost.