Purely functional data structures

Chris Okasaki9780521631242, 9780511530104, 0521663504, 0521631246, 0511530102, 9780521663502

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.

---

Table of contents :
Front cover……Page 1
Contents……Page 5
Preface……Page 9
1.1 Functional vs. Imperative Data Structures……Page 11
1.2 Strict vs. Lazy Evaluation……Page 12
1.3 Terminology……Page 13
1.5 Overview……Page 14
2.1 Lists……Page 17
2.2 Binary Search Trees……Page 21
2.3 Chapter Notes……Page 25
3.1 Leftist Heaps……Page 27
3.2 Binomial Heaps……Page 30
3.3 Red-Black Trees……Page 34
3.4 Chapter Notes……Page 39
4.1 $-notation……Page 41
4.2 Streams……Page 44
4.3 Chapter Notes……Page 47
5.1 Techniques of Amortized Analysis……Page 49
5.2 Queues……Page 52
5.3 Binomial Heaps……Page 55
5.4 Splay Heaps……Page 56
5.5 Pairing Heaps……Page 62
5.6 The Bad News……Page 64
5.7 Chapter Notes……Page 65
6.1 Execution Traces and Logical Time……Page 67
6.2 Reconciling Amortization and Persistence……Page 68
6.2.2 A Framework for Analyzing Lazy Data Structures……Page 69
6.3 The Banker’s Method……Page 71
6.3.1 Justifying the Banker’s Method……Page 72
6.3.2 Example: Queues……Page 74
6.3.3 Debit Inheritance……Page 77
6.4 The Physicist’s Method……Page 78
6.4.1 Example: Binomial Heaps……Page 80
6.4.2 Example: Queues……Page 82
6.4.3 Example: Bottom-Up Mergesort with Sharing……Page 84
6.5 Lazy Pairing Heaps……Page 89
6.6 Chapter Notes……Page 91
7 Eliminating Amortization……Page 93
7.1 Scheduling……Page 94
7.2 Real-Time Queues……Page 96
7.3 Binomial Heaps……Page 99
7.4 Bottom-Up Mergesort with Sharing……Page 104
7.5 Chapter Notes……Page 107
8.1 Batched Rebuilding……Page 109
8.2 Global Rebuilding……Page 111
8.2.1 Example: Hood-Melville Real-Time Queues……Page 112
8.3 Lazy Rebuilding……Page 114
8.4 Double-Ended Queues……Page 116
8.4.1 Output-Restricted Deques……Page 117
8.4.2 Banker’s Deques……Page 118
8.4.3 Real-Time Deques……Page 121
8.5 Chapter Notes……Page 123
9 Numerical Representations……Page 125
9.2 Binary Numbers……Page 126
9.2.1 Binary Random-Access Lists……Page 129
9.2.2 Zeroless Representations……Page 132
9.2.3 Lazy Representations……Page 135
9.2.4 Segmented Representations……Page 137
9.3 Skew Binary Numbers……Page 140
9.3.1 Skew Binary Random-Access Lists……Page 142
9.3.2 Skew Binomial Heaps……Page 144
9.4 Trinary and Quaternary Numbers……Page 148
9.5 Chapter Notes……Page 150
10 Data-Structural Bootstrapping……Page 151
10.1 Structural Decomposition……Page 152
10.1.1 Non-UnifonnRecursion and Standard ML……Page 153
10.1.2 Binary Random-Access Lists Revisited……Page 154
10.1.3 Bootstrapped Queues……Page 156
10.2 Structural Abstraction……Page 161
10.2.1 Lists With Efficient Catenation……Page 163
10.2.2 Heaps With Efficient Merging……Page 168
10.3.1 Tries……Page 173
10.3.2 Generalized Tries……Page 176
10.4 Chapter Notes……Page 179
11.1 Queues and Deques……Page 181
11.2 Catenable Double-Ended Queues……Page 185
11.3 Chapter Notes……Page 194
A Haskell Source Code……Page 195
Bibliography……Page 217
Index……Page 227
Back cover……Page 232