Purely functional data structures

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. 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 "Most books on data structures assume an imperative language like 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 so that programmers can develop their own functional data structures. It 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 can easily be adapted 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."--Jacket Chris Okasaki 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. He includes both classical data structures and a host of new data structures developed exclusively for functional languages.

This book describes data structures and data structure design techniques for functional languages.