Purely Functional Data Structures

In Section 9.2.3, we saw how lazy redundant binary numbers support both increment and decrement functions in O(1) amortized time. In Section 10.1.2, we saw how non-uniform types and polymorphic recursion afford particularly simple implementations of numerical representations such as binary random-access lists. In this chapter, we combine and generalize these techniques into a framework called implicit recursive slowdown.