Log In
Or create an account ->
Imperial Library
Home
About
News
Upload
Forum
Help
Login/SignUp
Index
Title
Copyright
Contents
Preface
1 Introduction
1.1 Functional vs. Imperative Data Structures
1.2 Strict vs. Lazy Evaluation
1.3 Terminology
1.4 Approach
1.5 Overview
2 Persistence
2.1 Lists
2.2 Binary Search Trees
2.3 Chapter Notes
3 Some Familiar Data Structures in a Functional Setting
3.1 Leftist Heaps
3.2 Binomial Heaps
3.3 Red-Black Trees
3.4 Chapter Notes
4 Lazy Evaluation
4.1 $-notation
4.2 Streams
4.3 Chapter Notes
5 Fundamentals of Amortization
5.1 Techniques of Amortized Analysis
5.2 Queues
5.3 Binomial Heaps
5.4 Splay Heaps
5.5 Pairing Heaps
5.6 The Bad News
5.7 Chapter Notes
6 Amortization and Persistence via Lazy Evaluation
6.1 Execution Traces and Logical Time
6.2 Reconciling Amortization and Persistence
6.2.1 The Role of Lazy Evaluation
6.2.2 A Framework for Analyzing Lazy Data Structur
6.3 The Banker’s Method
6.3.1 Justifying the Banker’s Method
6.3.2 Example: Queues
6.3.3 Debit Inheritance
6.4 The Physicist’s Method
6.4.1 Example: Binomial Heaps
6.4.2 Example: Queues
6.4.3 Example: Bottom-Up Mergesort with Sharing
6.5 Lazy Pairing Heaps
6.6 Chapter Notes
7 Eliminating Amortization
7.1 Scheduling
7.2 Real-Time Queues
7.3 Binomial Heaps
7.4 Bottom-Up Mergesort with Sharing
7.5 Chapter Notes
8 Lazy Rebuilding
8.1 Batched Rebuilding
8.2 Global Rebuilding
8.2.1 Example: Hood–Melville Real-Time Queues
8.3 Lazy Rebuilding
8.4 Double-Ended Queues
8.4.1 Output-Restricted Deques
8.4.2 Banker’s Deques
8.4.3 Real-Time Deques
8.5 Chapter Notes
9 Numerical Representations
9.1 Positional Number Systems
9.2 Binary Numbers
9.2.1 Binary Random-Access Lists
9.2.2 Zeroless Representations
9.2.3 Lazy Representations
9.2.4 Segmented Representations
9.3 Skew Binary Numbers
9.3.1 Skew Binary Random-Access Lists
9.3.2 Skew Binomial Heaps
9.4 Trinary and Quaternary Numbers
9.5 Chapter Notes
10 Data-Structural Bootstrapping
10.1 Structural Decomposition
10.1.1 Non-Uniform Recursion and Standard ML
10.1.2 Binary Random-Access Lists Revisited
10.1.3 Bootstrapped Queues
10.2 Structural Abstraction
10.2.1 Lists With Efficient Catenation
10.2.2 Heaps With Efficient Merging
10.3 Bootstrapping To Aggregate Types
10.3.1 Tries
10.3.2 Generalized Tries
10.4 Chapter Notes
11 Implicit Recursive Slowdown
11.1 Queues and Deques
11.2 Catenable Double-Ended Queues
11.3 Chapter Notes
A Haskell Source Code
Bibliography
Index
← Prev
Back
Next →
← Prev
Back
Next →