Functional Data Structures

1 Overview

This repository contains implementations of purely functional data structures based on Chris Okasaki’s book “Purely Functional Data Structures” and his PhD thesis. The implementations are available in two Lisp dialects:

• Guile Scheme 3.0+: A dialect of Scheme (a Lisp variant) that is part of the GNU project
• Hy 1.0+: A Lisp dialect embedded in Python, now with semantic macros and Scheme-inspired design

Hy 1.0 introduces a significant evolution in its design with a cleaner, more consistent semantic model. This makes it particularly well-suited for implementing functional data structures alongside Scheme.

2 References

• Okasaki, C. (1999). Purely Functional Data Structures. Cambridge University Press.
  • Goodreads Link
• Okasaki, C. (1996). Purely Functional Data Structures (PhD thesis). Carnegie Mellon University.
  • PDF Link

You can download the PhD thesis paper by running: make get-paper

3 Data Structures

The following data structures are implemented:

• Persistent Lists
• Stacks
• Queues (using the two-list approach)
• Binomial Heaps
• Red-Black Trees
• More to come…

4 Getting Started

4.1 Prerequisites

• Guile 3.0+ for the Scheme implementation
• Python 3.10+ with Hy 1.0+ for the Hy implementation
• Poetry for Python dependency management
• Emacs with org-mode for development

4.2 Installation

# Clone the repository
git clone https://github.com/aygp-dr/functional-data-structures.git
cd functional-data-structures

# Setup Python environment with Hy
poetry install

4.3 Running the Code

The source code is maintained in an Org-mode file (Literate Programming) and is “tangled” into separate Scheme and Hy files. The workflow is:

# Tangle org file into Scheme and Hy source code
make tangle

# Run the implementations
make run-scheme  # Run Scheme implementation
make run-hy      # Run Hy implementation

# Run tests
make test

# If you edit source files directly, you can sync changes back to the org file
make detangle

We use a bi-directional workflow where you can either:

1. Edit the okasaki-data-structures.org file and run make tangle to generate code, or
2. Edit files in the scheme/ and hy/ directories and run make detangle to update the org file

The tangled code files are marked as generated and can be cleaned with make clean. This approach lets us maintain parity between implementations while documenting concepts in a single place.

5 Structure

• okasaki-data-structures.org - Main source file in Org-mode
• scheme/ - Tangled Scheme source files
• hy/ - Tangled Hy source files
• tests/ - Test files for both implementations

6 Development with Emacs

This project is designed to be developed with Emacs using org-mode for literate programming. The included .emacs.d/init.el provides the necessary configuration for:

• Org-mode with syntax highlighting
• Babel for executing source blocks
• Tangle support for extracting code
• Geiser integration for Scheme development (using Guile by default)
• Hy-mode for Hy development

7 Contributing

Contributions are welcome! Please feel free to submit a Pull Request.

8 License

This project is licensed under the MIT License - see the LICENSE file for details.