The previous chapter introduced the idea of amortization and gave several examples of data structures with good amortized bounds. However, for each these data structures, the amortized bounds break in the presence of persistence. In this chapter, we demonstrate how lazy evaluation can mediate the conflict between amortization and persistence, and adapt both the banker's and physicist's methods to account for lazy evaluation. We then illustrate the use of these new methods on several amortized data structures that use lazy evaluation internally.

Execution Traces and Logical Time

In the previous chapter, we saw that traditional methods of amortization break in the presence of persistence because they assume a unique future, in which the accumulated savings will be spent at most once. However, with persistence, multiple logical futures might all try to spend the same savings. But what exactly do we mean by the “logical future” of an operation?

We model logical time with execution traces, which give an abstract view of the history of a computation. An execution trace is a directed graph whose nodes represent operations of interest, usually just update operations on the data type in question. An edge from v to v′ indicates that operation v′ uses some result of operation v.

I first began programming in Standard ML in 1989. I had always enjoyed implementing efficient data structures, so I immediately set about translating some of my favorites into Standard ML. For some data structures, this was quite easy, and to my great delight, the resulting code was often both much clearer and much more concise than previous versions I had written in C or Pascal or Ada. However, the experience was not always so pleasant. Time after time, I found myself wanting to use destructive updates, which are discouraged in Standard ML and forbidden in many other functional languages. I sought advice in the existing literature, but found only a handful of papers. Gradually, I realized that this was unexplored territory, and began to search for new ways of doing things.

Eight years later, I am still searching. There are still many examples of data structures that I just do not know how to implement efficiently in a functional language. But along the way, I have learned many lessons about what does work in functional languages. This book is an attempt to codify these lessons. I hope that it will serve as both a reference for functional programmers and as a text for those wanting to learn more about data structures in a functional setting.

Most of the time, we do not care whether a data structure has amortized bounds or worst-case bounds; our primary criteria for choosing one data structure over another are overall efficiency and simplicity of implementation (and perhaps availability of source code). However, in some application areas, it is important to bound the running times of individual operations, rather than sequences of operations. In these situations, a worst-case data structure will often be preferable to an amortized data structure, even if the amortized data structure is simpler and faster overall. Raman [Ram92] identifies several such application areas, including

• Real-time systems: In real-time systems, predictability is more important than raw speed [Sta88]. If an expensive operation causes the system to miss a hard deadline, it does not matter how many cheap operations finished well ahead of schedule.

• Parallel systems: If one processor in a synchronous system executes an expensive operation while the other processors execute cheap operations, then the other processors may sit idle until the slow processor finishes.

• Interactive systems: Interactive systems are similar to real-time systems ― users often value consistency more than raw speed [But83]. For instance, users might prefer 100 1-second response times to 99 0.25-second response times and 1 25-second response time, even though the latter scenario is twice as fast.

Although many imperative data structures are difficult or impossible to adapt to a functional setting, some can be adapted quite easily. In this chapter, we review three data structures that are commonly taught in an imperative setting. The first, leftist heaps, is quite simple in either setting, but the other two, binomial queues and red-black trees, have a reputation for being rather complicated because imperative implementations of these data structures often degenerate into nightmares of pointer manipulations. In contrast, functional implementations of these data structures abstract away from troublesome pointer manipulations and directly reflect the high-level ideas. A bonus of implementing these data structures functionally is that we get persistence for free.

Leftist Heaps

Sets and finite maps typically support efficient access to arbitrary elements. But sometimes we need efficient access only to the minimum element. A data structure supporting this kind of access is called a priority queue or a heap. To avoid confusion with FIFO queues, we use the latter name. Figure 3.1 presents a simple signature for heaps.

Remark In comparing the signature for heaps with the signature for sets (Figure 2.7), we see that in the former the ordering relation on elements is included in the signature while in the latter it is not.

Convexity is one of the oldest concepts in mathematics. It already appears in the works of Archimedes, around three centuries B.C. It was not until the 1950s, however, that this theme developed widely in the works of modern mathematicians. Convexity is a fundamental notion for computational geometry, at the core of many computer engineering applications, for instance in robotics, computer graphics, or optimization.

A convex set has the basic property that it contains the segment joining any two of its points. This property guarantees that a convex object has no hole or bump, is not hollow, and always contains its center of gravity. Convexity is a purely affine notion: no norm or distance is needed to express the property of being convex. Any convex set can be expressed as the convex hull of a certain point set, that is, the smallest convex set that contains those points. It can also be expressed as the intersection of a set of half-spaces. In the following chapters, we will be interested in linear convex sets. These can be defined as convex hulls of a finite number of points, or intersections of a finite number of half-spaces. Traditionally, a bounded linear convex set is called a polytope. We follow the tradition here, but we understand the word polytope as a shorthand for bounded polytope. This lets us speak of an unbounded polytope for the non-bounded intersection of a finite set of half-spaces.

Term rewriting is a branch of theoretical computer science which combines elements of logic, universal algebra, automated theorem proving and functional programming. Its foundation is equational logic. What distinguishes term rewriting from equational logic is that equations are used as directed replacement rules, i.e. the left-hand side can be replaced by the right-hand side, but not vice versa. This constitutes a Turing-complete computational model which is very close to functional programming. It has applications in algebra (e.g. Boolean algebra, group theory and ring theory), recursion theory (what is and is not computable with certain sets of rewrite rules), software engineering (reasoning about equationally defined data types such as numbers, lists, sets etc.), and programming languages (especially functional and logic programming). In general, term rewriting applies in any context where efficient methods for reasoning with equations are required.

To date, most of the term rewriting literature has been published in specialist conference proceedings (especially Rewriting Techniques and Applications and Automated Deduction in Springer's LNCS series) and journals (e.g. Journal of Symbolic Computation and Journal of Automated Reasoning). In addition, several overview articles provide introductions into the field, and references to the relevant literature [141, 74, 204]. This is the first English book devoted to the theory and applications of term rewriting. It is ambitious in that it tries to serve two masters:

• The researcher, who needs a unified theory that covers, in detail and in a single volume, material that has previously only been collected in overview articles, and whose technical details are spread over the literature.

• The teacher or student, who needs a readable textbook in an area where there is hardly any literature for the non-specialist.

The first part of this book introduces the most popular tools in computational geometry. These tools will be put to use throughout the rest of the book.

The first chapter gives a framework for the analysis of algorithms. The concept of complexity of an algorithm is reviewed. The underlying model of computation is made clear and unambiguous.

The second chapter reviews the fundamentals of data structures: lists, heaps, queues, dictionaries, and priority queues. These structures are mostly implemented as balanced trees. To serve as an example, red–black trees are fully described and their performances are evaluated.

The third chapter illustrates the main algorithmic techniques used to solve geometric problems: the incremental method, the divide-and-conquer method, the sweep method, and the decomposition method which subdivides a complex object into elementary geometric objects.

Finally, chapters 4, 5, and 6 introduce the randomization methods which have recently made a distinguished appearance on the stage of computational geometry. Only the incremental randomized method is introduced and used in this book, as opposed to the randomized divide-and-conquer method.

To compute the convex hull of a finite set of points is a classical problem in computational geometry. In two dimensions, there are several algorithms that solve this problem in an optimal way. In three dimensions, the problem is considerably more difficult. As for the general case of any dimension, it was not until 1991 that a deterministic optimal algorithm was designed. In dimensions higher than 3, the method most commonly used is the incremental method. The algorithms described in this chapter are also incremental and work in any dimension. Methods specific to two or three dimensions will be given in the next chapter.

Before presenting the algorithms, section 8.1 details the representation of polytopes as data structures. Section 8.2 shows a lower bound of Ω(n log n + n⌊d/2⌋) for computing the convex hull of n points in d dimensions. The basic operation used by an incremental algorithm is: given a polytope C and a point P, derive the representation of the polytope conv(C ∪ {P}} assuming the representation of C has already been computed. Section 8.3 studies the geometric part of this problem. Section 8.4 shows a deterministic algorithm to compute the convex hull of n points in d dimensions. This algorithm requires preliminary knowledge of all the points: it is an off-line algorithm. Its complexity is O(n log n + n⌊(d+1)/2⌋), which is optimal only in even dimensions.