[Haskell] Re: Queues / Lists with unbound tails

[Robert Will]

On Sat, 8 May 2004, andrew cooke wrote:
>
> I'm trying to write a simple fifo queue of fixed length (containing type
> Maybe a - it would be initialised to Nothings) where pushing an item pops
> the "last" item "off the end".
>
> data Queue a = QUEUE (Maybe a -> (Queue a, Maybe a))
>
> queue :: Maybe a -> Queue a
> queue n1 = QUEUE (\n2 -> (queue n2, n1))

I suppose, push/pop in this implementation is just function application.
so if
  q :: Queue a
I can write:
(q', top) = q new_elem

q' and q have the same length.

> consQ :: Queue a -> Queue a -> Queue a
> consQ (QUEUE q1) (QUEUE q2) =
>   QUEUE (\n -> let (q1', n1) = q1 n
>                    (q2', n2) = q2 n1
>                in (consQ q1' q2', n2))
>
> works, and lets me construct arbitrary length queues, but the push/pop
> operation is O(n) (I believe) in the length of the queue.

> I don't have Okasaki's book with me, but I'm pretty sure he gives a
> solution that has two lists, with the second inverted via an operation
> that is either amortized O(1), or inverted stepwise using lazy evaluation.

Source and explanation of those algorithms are part of my Dessy project:
http://www.stud.tu-ilmenau.de/~robertw/dessy/fun/Queue.hs

The two-list solution is also the only purely functional way to achieve
this efficiency for Queues.  The solution that "opens the closures" is
imperative in essence (and probably better implemented in an imperative
language).


Robert