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 <[email protected]>
