functional data structures for scheme
Scheme Shell
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Failed to load latest commit information.
deques
doc
examples
private
queues
tests
.gitignore
LICENSE
README.org
bbtrees.sls
deques.sls
dlists.sls
fingertrees.sls
hamts.sls
heaps.sls
pkg-list.scm
psqs.sls
queues.sls
runtests
sequences.sls
sets.sls
tests.scm

README.org

Purely Functional Data Structures in Scheme -*- org -*-

About

pfds is a set of purely functional data structures written in R6RS Scheme. It has been tested with Racket, Guile 2, Vicare Scheme and IronScheme. Right now it contains

  • queues
  • deques
  • bbtrees
  • sets
  • dlists
  • priority search queues (psqs)
  • finger trees
  • sequences
  • heaps
  • hamts

with more to come, time permitting.

Installation

Just clone it somewhere on your $GUILE_LOAD_PATH and you’re done. Alternatively, a pkg-list.scm file is provided for use with the dorodango package manager.If you want to run the tests file, you will need trc-testing from the wak project.

Documentation

Documentation is provided at the top of the respective files. The queues and deques are based on the paper “Simple and Efficient Purely Functional Queues and Deques” by Chris Okasaki. The bbtrees and sets are based on the paper “Implementing Sets Efficiently in a Functional Language” by Stephen Adams.

Dlists are a well known trick in the functional programming community, going back to at least “A Novel Representation of Lists and its application to the Function “Reverse”” by John Hughes in 1984, although he does not give them this name. The trick is likely even older than that (he points to a paper by Bird), though I have not the knowledge to confirm this.

The implementation of priority search queues is described in “A Simple Implementation Technique for Priority Search Queues” by Ralf Hinze.

The heaps use a height-biased leftist tree implementation.

Finger trees are described in Finger trees: a simple general-purpose data structure by Ross Paterson and Ralf Hinze.

Hash Array Map Tries are described in the paper Ideal Hash Trees by Phil Bagwell.

Thanks

Thanks to Llewellyn Pritchard for testing this on IronScheme, to Marco Maggi for testing on Vicare Scheme, and to Andy Wingo for pointing out priority search queues to me, and prodding me into implementing them.