Purely Functional Data Structures in C++

Yet another implementation of the immutable data structures in Okasaki's textbook, "Purely Functional Data Structures", in C++.

Requirements

A C++20 compatible compiler is necessary. For instance, g++ 10.2.0 with -std=c++20 flag compiles the codes successfully.

Disclaimers

• The code is at a very early stage. There should be bugs and rough edges.

• In Chapter 10 and 11, we need a polymorphic recursion. Although the static typing system of C++ forbids a proliferation of infinite number of types at compile time (i.e., a genuine polymorphic recursion), we can introduce the auxiliary cutoff for the number of the recursions with constexpr-if; If the depth of the recursion exceeds this cutoff number, the runtime exception is thrown. I will use this pseudo "polymorphic recursion".

List of data structures

Chapter 2

• List
• Binary Search Tree

Chapter 3

• Leftist Heap
• Weight Biased Leftist Heap
• Binomial Heap
• Explicit Minimum Binomial Heap
• Red Black Tree
• Red Black Tree with not-so-efficient-delete

Chapter 4

• Stream (with O(n*k) insertion sort)

Chapter 5

• Queue
• Deque
• Splay Heap
• Pairing Heap

Chapter 6

• Bankers Queue
• Lazy Binomial Heap
• Physicists Queue
• Bottom Up Merge sort
• Lazy Pairing Heap

Chapter 7

• Real Time Queue
• Scheduled Binomial Heap
• Scheduled Bottom Up Merge Sort

Chapter 8

• Hood Melville Queue
• Bankers Deque
• Real Time Deque

Chapter 9

• Binary Random Access List
• Skew Binary Random Access List
• Skew Binomial Heap

Chapter 10

• Alt Binary Random Access List
• Bootstrapped Queue
• Catenable List
• Trie
• Hash Table
• Trie of Trees

Chapter 11

• Implicit Queue
• Simple Catenable Deque
• Implicit Catenable Deque

References

okasaki: Purely Functional Data Structures

type erasure: C++ Templates - The Complete Guide

lazy evaluation: Functional Programming in C++