[Haskell] Queues / Lists with unbound tails

[andrew cooke]

Hi,

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

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.

However, it seems to me that there should be another solution, with a
lazily constructed list whose tail does not yet exist.  The queue would
consiste of the head of the list (which is the "tail" of the queue!) and a
closure that extends the list tail (ie the queue head).

Pushing an element would involve invoking the closure, extending the tail
of the (lazily constructed) list, and returning another closure to
continue the process.  The return ("pop") value would be the head of the
list, with the next item carried forward as the next return value.

I think this would be simple to implement in Prolog or Oz, for example,
where the last element of a list can be unbound.  I assume the same is
possible in Haskell using laziness and closures.

However, I cannot nail it down.  Can anyone help?

Apologies for the unclear description.  If I could describe the solution
clearly then I could write the code and wouldn't need to ask :o)

Thanks,
Andrew

-- 
` __ _ __ ___  ___| |_____   work web site: http://www.ctio.noao.edu/~andrew
 / _` / _/ _ \/ _ \ / / -_)  personal web site: http://www.acooke.org/andrew
 \__,_\__\___/\___/_\_\___|  list: http://www.acooke.org/andrew/compute.html