Purely Functional Data Structures

Solutions for "Purely Functional Data Structures" by Chris Okasaki.

2 Persistance

2.1 Lists

• Exercise 2.1 (image)

2.2 Binary Search Tree

• Exercise 2.2
• Exercise 2.3
• Exercise 2.4
• Exercise 2.5 (a) (b)
• Exercise 2.6

3 Some Faimiliar Data Structures in a Functional Setting

3.1 Leftist Heaps

• Exercise 3.1
• Exercise 3.2
• Exercise 3.3
• Exercise 3.4 (a) (b) (c) (d)

3.2 Binomial Heaps

• Exercise 3.5
• Exercise 3.6
• Exercise 3.7

3.3 Red-Black Trees

• Exercise 3.8
• Exercise 3.9
• Exercise 3.10 (a) (b)

4 Lazy Evaluation

4.1 $-notation

4.2 Streams

• Exercise 4.1
• Exercise 4.2 (process)

5 Fundamentals of Amortization

5.1 Techniques of Amortized Analysis

5.2 Queues

• Exercise 5.1 (a) (b) (b ja)

5.3 Binomial Heaps

• Exercise 5.2 (ja)
• Exercise 5.3 (ja)

5.4 Splay Heaps

• Exercise 5.4
• Exercise 5.5
• Exercise 5.6
• Exercise 5.7

5.5 Pairing Heaps

• Exercise 5.8 (a) (b) (c)

5.6 The Bad News

• Exercise 5.9

6 Amortization and Persistence via Lazy Evaluation

6.1 Execution Traces and Logical Time

• Exercise 6.1

6.2 Reconciling Amortization and Persistence

6.3 The Banker's Method

• Exercise 6.2 (a) (b)

6.4 The Physicist's Method

• Exercise 6.3
• Exercise 6.4
• Exercise 6.5
• Exercise 6.6 (a) (b)
• Exercise 6.7 (a) (b)

6.5 Lazy Pairing Heaps

7 Eliminating Amortization

7.1 Scheduling

7.2 Real-Time Queues

• Exercise 7.1 (src)
• Exercise 7.2 (src)

7.3 Binomial Heaps

• Exercise 7.3
• Exercise 7.4

7.4 Bottom-Up Mergesort with Sharing

8 Lazy Rebuilding

8.1 Batched Rebuilding

• Exercise 8.1

8.2 Global Rebuilding

• Exercise 8.2 (src)
• Exercise 8.3

8.3 Lazy Rebuilding

8.4 Double-Ended Queues

• Exercise 8.4
• Exercise 8.5
• Exercise 8.6
• Exercise 8.7

9 Numerical Representations

9.1 Positional Number Systems

9.2 Binary Numbers

• Exercise 9.1
• Exercise 9.2
• Exercise 9.3
• Exercise 9.4
• Exercise 9.5
• Exercise 9.6
• Exercise 9.7
• Exercise 9.8
• Exercise 9.9 (src)
• Exercise 9.10
• Exercise 9.11
• Exercise 9.12
• Exercise 9.13

9.3 Skew Binary Numbers

• Exercise 9.14 (demo)
• Exercise 9.15
• Exercise 9.16 (demo)

9.4 Trinary and Quatenary Numbers

• Exercise 9.17 (demo)
• Exercise 9.18 (demo)
• Exercise 9.19 (demo)

10 Data-Structual Bootstrapping

10.1 Structual Decomposition

• Exercise 10.1
• Exercise 10.2
• Exercise 10.3
• Exercise 10.4
• Exercise 10.5 (a) (b)

10.2 Structual Abstraction

• Exercise 10.6
• Exercise 10.7
• Exercise 10.8

10.3 Bootstrapping To Aggregate Types

• Exercise 10.9
• Exercise 10.10
• Exercise 10.11
• Exercise 10.12
• Exercise 10.13
• Exercise 10.14
• Exercise 10.15

11 Implicit Recursive Slowdown

11.1 Queues and Deques

• Exercise 11.1
• Exercise 11.2

11.2 Catenable Double-Ended Queues

• Exercise 11.3
• Exercise 11.4