Hi all,

While preparing the SRFI 134 package for CHICKEN, I read through
Chris Okasaki’s banker’s-deque presentation (in _Purely Functional
Data Structures_, Cambridge 1998), which is the basis of Shiro’s
two-list SRFI 134 implementation.  Okasaki’s analysis of banker’s deques
(p. 109–110) seems to rely on lazy rebuilding; that is, the amortized
constant-time performance of these deques assumes a two-*stream* (lazy
list) representation.  The details could be a bit clearer (Okasaki very
helpfully leaves part of the analysis as an exercise), but it seems to
me that an eager two-list implementation can’t meet the running-time
guarantees stated in the SRFI--in particular, all of the O(1)-time
queue operations[*].

I’ve adapted Shiro’s implementation to a two-stream ideque
representation, using SRFI 41 streams.  If I’ve understood Okasaki,
then this implementation should provide amortized constant-time
deque operations; if the authors are willing, I’d like to add it
to contrib/.  If you think I haven’t understood the analysis, please
help me out. :)

It’s possible to replace the streams with lseqs from SRFI 127, as John
suggested (on IRC).  I chose streams for convenience; the stream library
is much bigger than SRFI 127, and I still had to implement several basic
stream operations.

Thanks to Shiro for providing the two-list sample implementation.

Best regards, Wolf

[*]: Strictly speaking, these should be revised to “amortized O(1)
time”, unless there’s an immutable deque implementation out there
that really can do constant-time deque operations.

--
Wolfgang Corcoran-Mathe  <xxxxxx@sigwinch.xyz>