Purely Functional Data Structures
Format: PDF / Kindle (mobi) / ePub
Most books on data structures assume an imperative language such as C or C++. However, data structures for these languages do not always translate well to functional languages such as Standard ML, Haskell, or Scheme. This book describes data structures from the point of view of functional languages, with examples, and presents design techniques that allow programmers to develop their own functional data structures. The author includes both classical data structures, such as red-black trees and binomial queues, and a host of new data structures developed exclusively for functional languages. All source code is given in Standard ML and Haskell, and most of the programs are easily adaptable to other functional languages. This handy reference for professional programmers working with functional languages can also be used as a tutorial or for self-study.
Eliminating Amortization ing [Ove83], which will be discussed further in the next chapter. Their implementation does not use lazy evaluation and is more complicated than ours. 8 Lazy Rebuilding The remaining four chapters describe general techniques for designing functional data structures. We begin in this chapter with lazy rebuilding, a. variant of global rebuilding [Ove83]. 8.1 Batched Rebuilding Many data structures obey balance invariants that guarantee efficient access. The canonical
nodes increases by one. We also assign a debit to the root of t'm_1 because the last call to linkAII is suspended even though it does not call 158 Data-Structural Bootstrapping link. Since the degree of this node does not change, we immediately discharge this final debit. Now, suppose the ith node of t appears in tj. By the left-linear debit invariant, we know that Dt(i) < i + deptht(i), but consider how each of these quantities changes with the tail, i decreases by one because
will account for the fact that both the type of 10.2 Structural Abstraction 159 elements and the comparison function on those elements are fixed at functorapplication time. Under the above assumption, the type of bootstrapped heaps can be given as datatype a Heap = E | H of a x (a Heap) PrimH.Heap where PrimH is the implementation of primitive heaps. The element stored at any given H node will be the minimum element in the subtree rooted at that node. The elements of the primitive heaps are
161 functor Bootstrap (functor MakeH (Element: ORDERED) : HEAP where type Elem.T = Element.T) (Element: ORDERED) : HEAP = struct structure Elem = Element (* recursive structures not supported in Standard ML! *) structure rec BootstrappedElem = struct datatype T = E | H of Elem.T x PrimH.Heap fun leq (H (x, _), H (y, _)) = Elem.leq (x, y) ... similar definitions for eq and It... end and PrimH = MakeH (BootstrappedElem) open BootstrappedElem (* expose E and H constructors *) type Heap =
binomial heap of size n correspond exactly to the ones in the binary representation of n. For example, the binary representation of 21 is 10101 so a binomial heap of size 21 would contain one tree of rank 0, one tree of rank 2, and one tree of rank 4 (of sizes 1,4, and 16, respectively). Note that, just as the binary representation of n contains at most [log(n + 1)J ones, a binomial heap of size n contains at most [log(n + 1) J trees. We are now ready to describe the functions on binomial heaps.