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