make-queue-with-list and make-queue-with-first-last Takashi Kato (04 Dec 2014 19:37 UTC)
Re: make-queue-with-list and make-queue-with-first-last Shiro Kawai (04 Dec 2014 20:15 UTC)
Re: make-queue-with-list and make-queue-with-first-last John Cowan (05 Dec 2014 12:39 UTC)
Re: make-queue-with-list and make-queue-with-first-last John Cowan (05 Dec 2014 12:36 UTC)
Re: make-queue-with-list and make-queue-with-first-last Kevin Wortman (05 Dec 2014 20:43 UTC)
New release of SRFI 117 John Cowan (06 Dec 2014 02:00 UTC)
Re: New release of SRFI 117 Takashi Kato (06 Dec 2014 09:27 UTC)
Re: New release of SRFI 117 John Cowan (06 Dec 2014 17:27 UTC)
Re: New release of SRFI 117 Kevin Wortman (06 Dec 2014 22:39 UTC)
Re: New release of SRFI 117 John Cowan (06 Dec 2014 22:52 UTC)

Re: make-queue-with-list and make-queue-with-first-last Shiro Kawai 04 Dec 2014 20:16 UTC

I've been pondering this, too - whether this srfi should specify
underlying implementation or not.  Gauche also has a queue library,
which now use lists internally but I was about to introduce
alternative implementation using a ring buffer.

OTOH, the intention of this srfi is understandable - that,
by exposing internal list structure, we can use rich list
utitities instead of duplicating them for queue, e.g. queue-find,
queue-any, queue-every etc.

Arguably, this makes the proposed API low-level - for example,
if an implementation wants to provide a variation of a queue
which is MT-safe, API to expose its internal list won't make
much sense.  One need to build a distinct structure which
internally use this srfi.

Maybe what bothers me most is that this specific implementation
strategy takes a generic name "queue".   It'd be nice that
a generic queue-add-front! etc work with various queue
implementations.

Will it be too confusing to name this as simple-queue or list-queue
or something?

>From: Takashi Kato <xxxxxx@ymail.com>
Subject: make-queue-with-list and make-queue-with-first-last
Date: Thu, 04 Dec 2014 20:37:13 +0100

> Hi,
>
> I'm wondering why these 2 procedures are separated. Since an list
> argument can be also first pair of the list, I think the
> `make-queue-with-list` procedure can be like this:
>
> (make-queue-with-list first [last])
>
> Beside this, the description of `make-queue-with-list` seems forcing
> implementations to use a list as its storage. I think this is a bit
> over specifying. For example, Sagittarius also has queue library and
> it's implemented with deque which doesn't use a list as its storage.
> Thus it's impossible to build this SRFI on top of the library. Because
> of this, it is also impossible to satisfy O(1) required by
> `make-queue-with-first-last`.
>
>
> --
> _/_/
> Takashi Kato
> E-mail: xxxxxx@ymail.com
>