[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

ANN: pfds v0.2

From: Ian Price
Subject: ANN: pfds v0.2
Date: Fri, 23 Nov 2012 16:02:07 +0000
User-agent: Gnus/5.13 (Gnus v5.13) Emacs/23.3 (gnu/linux)

Hi folks,

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

Guildhall/Dorodango users can access it from my repository[1]
Simply use "guild update" to obtain the latest repository, and then
either "guild install pfds" or "guild upgrade" if you already have
version 0.1 installed.

* 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.
1. If you are not using it already, you can get started by reading
Ian Price --

"Programming is like pinball. The reward for doing it well is
the opportunity to do it again" - from "The Wizardy Compiled"

reply via email to

[Prev in Thread] Current Thread [Next in Thread]