You are previewing Purely Functional Data Structures.
O'Reilly logo
Purely Functional Data Structures

Book Description

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.

Table of Contents

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