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]> >
