I think you should (with the permission of the SRFI implementation's author, who is me) promote Wolfgang's implementation to the main directory, since it is conformant and the present implementation is not. A suitable note would be: "Because the original implementation based on lists, by John Cowan, was found to be non-conformant, the present implementation by Wolfgang Corcoran-Mathe has replaced it, and his name has been added to the list of authors."
On Wed, Sep 14, 2022 at 5:24 AM Shiro Kawai <[email protected]> wrote: > Excellent catch. > In fact, Gauche's version uses Gauche's built-in lazy sequence feature > (lappend); when I adapted it to R7RS I rewrote it with eager list > concatenation but didn't realize that it would change the complexity. > > --shiro > > > On Sun, Sep 11, 2022 at 7:34 AM Wolfgang Corcoran-Mathe <[email protected]> > wrote: > >> 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]> >> >
