pfds
pfds copied to clipboard
ijp
functional data structures for scheme
- 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 [[http://gitorious.org/wak][wak project]].
** Documentation Documentation is provided at the top of the respective files. The queues and deques are based on the paper [[http://www.eecs.usma.edu/webs/people/okasaki/pubs.html#jfp95]["Simple and Efficient Purely Functional Queues and Deques"]] by Chris Okasaki. The bbtrees and sets are based on the paper [[http://groups.csail.mit.edu/mac/users/adams/BB/92-10.ps]["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 [[http://www.cs.tufts.edu/~nr/cs257/archive/john-hughes/lists.pdf][“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 [[http://www.cs.ox.ac.uk/people/ralf.hinze/publications/UU-CS-2001-09.pdf]["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 [[http://www.soi.city.ac.uk/~ross/papers/FingerTree.html][Finger trees: a simple general-purpose data structure]] by Ross Paterson and Ralf Hinze.
Hash Array Map Tries are described in the paper [[http://lampwww.epfl.ch/papers/idealhashtrees.pdf][Ideal Hash Trees]] by Phil Bagwell.
** Thanks Thanks to [[https://github.com/leppie][Llewellyn Pritchard]] for testing this on [[https://ironscheme.codeplex.com/][IronScheme]], to [[https://github.com/marcomaggi][Marco Maggi]] for testing on [[https://github.com/marcomaggi/vicare][Vicare Scheme]], and to [[http://wingolog.org/][Andy Wingo]] for pointing out priority search queues to me, and prodding me into implementing them.
ijp