Hello,
Here's a paper about purely functional queues by Chris Okasaki:
http://www.eecs.usma.edu/webs/people/okasaki/pubs.html#jfp95
I put an implementation of the queues up at (dharmalab misc queue):
http://github.com/dharmatech/dharmalab/raw/master/misc/queue.sls
Specifically, the implementation is based on what he describes in
section 5 "Queues with pre-evaluation".
The implementation also uses the awesome Streams Library by Philip Bewig
(SRFI 41).
How about an example usage?
Agave comes with a 'trails' demo. The original implementation used a
circular list to store the trail elements.
I've added a new demo called 'growable-trails' to agave. This one stores
the trail as a functional queue. Hold the right mouse button to grow the
trail. Hold the left mouse button to shrink the trail.
To run the demo:
$ ikarus --r6rs-script ~/agave/demos/growable-trails.sps
To install Agave:
$ cd ~/scheme
$ bzr branch lp:~scheme-libraries-team/scheme-libraries/srfi
$ git clone git://github.com/dharmatech/dharmalab.git
$ git clone git://github.com/dharmatech/agave.git
where '~/scheme' is the path to your Scheme libraries.
Browse the growable-trails source:
http://github.com/dharmatech/agave/raw/master/demos/growable-trails.sps
Ed
