Re: bugs in queue operations

On Thu, 24 Dec 2009 18:09:27 -0500
Taylor R Campbell <[email protected]> wrote:

>    Date: Thu, 24 Dec 2009 11:59:09 -0800
>    From: Robert Ransom <[email protected]>
> 
>    Yes, when I was still thinking about ways to optimize
>    DELETE-FROM-QUEUE!.  Our mutation-based queue implementations allow
>    both ENQUEUE! and DEQUEUE! to be implemented in constant time; I am not
>    aware of any functional data structures which would allow this.
> 
> For the standard functional queue implemented by a pair of stacks,
> ENQUEUE and DEQUEUE run in constant amortized time.  QUEUE-HEAD can
> lose and run in linear time, but it could be internally destructive in
> order to run in constant amortized time.  The operations running in
> constant amortized time can, as usual, at the cost of some overhead,
> be adapted to do the work incrementally and thereby run in constant
> real time.

I didn't know there was a standard functional queue data structure, but
I think I understand what you're describing.  It sounds like a good
idea to me, too.

>    I have attached to this message a bug-fix patch for Taylor Campbell's
>    queue package, and a Mercurial bundle for Scheme 48 that simplifies my
>    QUEUES package and then changes it to use his data structure.
> 
> Oops -- thanks.  The operations with the bugs you found are, of
> course, among those that I never actually use myself.  (For that
> matter, I pretty much never use anything but ENQUEUE!, DEQUEUE!,
> QUEUE-EMPTY?, and QUEUE-HEAD.)  I'll apply the fixes when I get a
> chance.

They are not used anywhere in Scheme 48, either.  (Also, your
PROVISIONAL-LIST->QUEUE, LIST->QUEUE!, and QUEUE->LIST! procedures are
not exported, because they are not in the interface of the Scheme 48
QUEUES structure.)

You might also want to copy my queue test suite into your repository
and modify it to work with your queue implementation; the test suite
has kept a few bugs out of the Scheme 48 repository already.

Robert Ransom