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.
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 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 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.