PFDS v0.2 released

Nov 23, 2012 at 3:03 PM

After 11 months, I've decided to release version 0.2 of pfds.

* What is it?

pfds is a collection of purely functional data structures, written in
pure R6RS Scheme. It is intended to be portable across a number of
different Scheme implementations, and has been tested on Guile 2.0,
Racket 5.2, and trunk IronScheme[0].

* What's changed?

** Changes to existing modules

- (pfds bbtrees)
  'bbtree-ordering-procedure' has been documented.

- (pfds sets)
  'set-ordering-procedure' has been exported and documented.

- (pfds queues)
  The procedures 'list->queue' and 'queue->list' have been added and

- (pfds deques)
  The procedures 'list->deque' and 'deque->list' have been added and

** Bug Fixes

- (pfds deques)
  The sizes of the streams stored in the deque data structure were
  being updated incorrectly. This would result in frequent errors when
  using the deques module. This has been corrected.

** New Modules

Since last release, I have added five new modules. They are all
documented at the top of the respective files.

- (pfds dlists)
  dlists are a well known trick in the functional programming for
  representing lists with efficient append.

- (pfds psqs)
  psqs or "priority search queues" are a combination of heaps and
  finite maps. These were added at the suggestion of Andy Wingo.

- (pfds heaps)
  A simple priority queue implementation based on leftist heaps.
- (pfds fingertrees)
  A generalisation of deques, that allow for incrementally maintaining
  an aggregate value.

- (pfds sequences)
  A generic sequence implementation written as an example of how to
  use fingertrees.

* Where can you get it?

Source code is available on github

* The future

For version 0.3, I'd like to add a few additional data structures,
such as HAMTs if at all feasible. I also intend to work on optimizing
the existing implementations, since the constant factors can be quite

If you have any functional data structures you would like added, that
you just want to tell me about, bug reports, feature requests,
examples or benchmarks you'd like me to do better on, do email me.


0. Thank you leppie.

Nov 23, 2012 at 4:42 PM

Thanks ijp :)

Included in the latest commit.