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 Quick Start

# Install dependencies
make install

# Run all tests and verify everything works
make test-scheme  # Scheme tests (fully working)

# Test individual implementations  
make run-scheme   # Load and test Scheme stack module
make run-hy       # Load and test Hy stack module

# Show all available commands
make help

4.4 Development Workflow

The project uses a literate programming approach with Org-mode, but also supports direct modular development:

1. **Modular Development** (Recommended):
   • Edit files directly in scheme/okasaki/ and hy/okasaki/ directories
   • Run make detangle to sync changes back to the org file
   • Use make test-scheme to run tests
2. **Literate Programming**:
   • Edit the okasaki-data-structures.org file
   • Run make tangle to generate modular code files
   • The tangled files are marked as generated
3. **Testing**:
   • make test-scheme - Run Scheme tests (✅ Working)
   • make test-hy - Run Hy tests (⚠️ In progress - modules load correctly)

The project maintains both approaches to support different development preferences while ensuring the implementations stay in sync.

5 Project Status

5.1 ✅ Working Components

• Scheme implementation with full test suite
• Hy implementation with module loading
• Build system with tangle/detangle workflow
• Proper module organization for both languages
• Comprehensive Makefile with all common tasks

5.2 ⚠️ In Progress

• Hy test infrastructure (modules work, pytest integration needs work)
• Additional data structures beyond stacks

6 Structure

• okasaki-data-structures.org - Main source file in Org-mode (literate programming)
• scheme/okasaki/ - Modular Scheme implementation files
• hy/okasaki/ - Modular Hy implementation files
• tests/scheme/ - Scheme test files (working)
• tests/hy/ - Hy test files (in progress)
• Makefile - Build system with comprehensive targets

7 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

8 Contributing

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

9 License

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